I

f.V.B.$Cr Gomputer
F
f-
Sem I
Section-l Section-ll

Expected Questions Paper Solutions

\

a
I
I

CHAPTERWISE YEARWISE

Paper-ll

Theoretical GomPuter
Science
/IS i11,.;

l, 8'.,.r:,
",;'' .

o t,r$r0il PUBHCffiI0tl$
\
 t
ection-!
Expected Questions (Ghapterwise)
Chapterl Preliminaries
o,
t-.4.,,*..)d Chapter 2 Finite Automata
!r8r0lt PUBuG0I|0[$ Chapter 3 Regular Language
Chapter 4
|9/1, Budhwar Peth, Appa Balwant Chowk, Pune - 2.
vebsite: ww t',visioDpune. com
Context Free Grammar and Languages
)Eail: visionpublications@gmail,com Chapter5 PushdownAutomata
info@visionpune.com
Chapter 6 Turing Machine

f heorctic al Com puter Sc lence

f.Y. B.Sc. (Computer Science) Sem I
Section-ll
Paper Solutions

Edition:
First: 2015
Jecood:2016

{ll rights reserved by Vision Publications. No part ofthis book is to be reproduced or transmitted in
rny fom, Electonic, Mechanical, Photocopy or any information stored in a retrieval system without
orior permission in writing, fiom Vision Publications, nor be otherwise circulated in any form of
binding or cover other than that in which it is published without a similar condition being imposed
@
ln the subsequent purchaser.

Printer
ulsl0lt
AP Vision Design & Prinls Plt Ltd, S.No. 83-2, Shivne Ind. Area, NDA Rd., Pune-23

Note: Due care has been taken while editing, printing and binding ofthe book. Neither the editon
nor publishen of the book hold any r€sponsibility for any mistake that may have inadvertently crept
in.
[f you notice any errors in
the book and wish to
report, please login our to
website www.visionpune.com and write comments on this book on the site. You can search this
book by entering Book ID mentioned below. Thank you.

@
 tl

www,visionPune.com
1. Onllne book storo (Checksolect'Buy)

2. Know dlf,eronl couBes at a glanco' tr Answer the followin (1 Mark Questi

Ma*s for these Questions may vary fmm 1 to 2
3. Complsto contents & olhe. dotall! at a glanco'

4. qubk Soarqh for books ot dlflerent Unlvorslllos' 1, Define prerix and list all profixos of ths string "xyz". (October 2012)
Solution
5, Opsn your account & gsl dbcount Polnls on each Pulcha3e'
A prefix ofa sting is any number of leading symbols ofthat string
6. Gottho book at your doo., don't wasto tlmo
& money on petrol'
I Prefix ofstring'xyz' = {s, x, xy, xyz}
7. Know the top solllng E speclal books along
wlth new arrlval!'
2. Let A = {a, b} and B = {e, d}. rind A x g. (October 2012)
Eonogolutlonlorallyournged!.ToxtBooks/PaPorsolutlon&compolltlveExams. Solu0on
A={a,b} andB=(e.d}
A x B = {(a e), (a, d), (b, e), (b, d)}
3. ff A = {E} then what is the valuo of lAl? 6pfl 2013)
Solu6on
e is empty string so its length lAl = 0
i lt
4. Let A = {a, b, c} and B = {1, 2, 3}, then writo the Cartesian product of A and B.
(October 2013)
Solution
doo!(!
A x B = ((a, 1), (a,2), (a, 3), (b, 1), (b, 2), (b, 3), (c, l), (c, 2), (c, 3))
,,."'
5. Define term "Empty string" vuith examplo' (Apil 2014)
I Free 5hipping
Solution
I

pI j
6.
Empty string is a string which has only ore member e and is rcpresented as (e )

Solution
What is ths value of n, where n = lel? @pfl 2014)

.ri 'qrfr l Value ofn where n = lel = 0.

-!ry1,.i11'I;::,r. ,.i. ,

7.
-&*!"'
w State truelfalse: ProPer suffix sot subsst of suffix set.

ffis
Solution
I
True

W visionpublications@gmail.com
8.
Solution
Stato true/false: Lsngth of string

False
't' is non"zero.

(%
T.Y. P ll-Theoretical Computer Sciencei . Preliminaries ut8t0i

\
 . . Preliminarios
a T.Y. P ll. Thsoretlcal Computor Sclence I . Prellminades (^
T.Y. P lt- Theoreiical Computer Science @ u$0i ullt0r

Stato the standard operations on Languages'

c. Ll = set of strings ending in 0; L2 = set ofstrings beginning with 01.

lution Ll . L2 = set ofstrings containing 001 as a substring.

Union d. L"{{}=1.1"0=0.
Concatenation
Closure
iii. Kleene clNure (*): The Kleene closure (or closure) ofl-, denotes L, is the set.
00

. Find the answer e LFl =? L* = ('-,/ i

i<)
lution
L*= e Lil
eLil=L*
Kleene closure is concatenation of zero or more elements with itself. It is a unary opemtion
, Define regular expression. ntoduced by Stephe n Klee ne.
,lution
follows:
Exanple, i. R1= {1}
A Regular Expression (RE) over the alphabet E is defined as
R1'= {e, 1,11, lll, I ll1....)
0 is a RE conesponding to fie empty language 0' ii. R1 = {ll, t0}
e is a RE coresPonding to the language {e). ftl'= (e, ll, 10, llll,l0l0, I110, 1011....)
For each symbol a e E, a is a RE conesponding to the language {a}' iii. O' = {€} - Kleene star applied on empty set

For any RE, r and s over E, conesponding to the languages !

and.L" respectively each ofthe
followLg is a regular expression conesponding to the language indicated'
2, State any five regular oxprcssion identltiea.
a. (rs) conesponding to the language I.L'. solullon

b. (r + s) corresponding to i" L (I" u I4).

+ Following are the identities for RE:

c, r+ corresponding to language I-*

i. AssociativityatrdCommutstivity

Only those "formulas" that can be produced by application ofrules I thrcugh 4 are Regular 1. L+M=M+L
expression over E. 2. (L+M)+N=L+(M+N)
3. (LM)N = L(MN)

!l f a pw r t.tp tg! !
ow_r! g-{ 9- M gI l!9- age-stiqFli Here note that LM * ML
I Marks for tl}€se Questions may vary fmm 4 to 5 ii, Dlstributivity
Explain with example Standard operations on languagos' l. L(M+N)=LM+LN
)lution 2. (M+N)L=ML+NL
Union: Given languages Lr and L2 we define their union to be the language Lr u L2= {x I x e iii. Identitics md AnhilatoN
L1 ORx e L, )
l $+1=L11=1
Cotrcatenation: Given languages L1 and L2 we define their concatenation to be the
language
2. eL=Le=L
Lr olz= ( xy lx e Ll andY e L2 } i 3. 0L=10=0
Ex. l
iv. Idempotent Loy
a. Ll = {he o} and L2 = {world} then Ll " L2 = {}rslloworld} I. L+L=L
b. L1 = [00, l0); L2 = {0, l}. Ll 'L2 = {000,001, 100, 101}
 th
T.Y. P ll- Theoretical computer Science I E . Prsliminaries ursl0I

Closure Laws
I (L)'= L' Fimito Atttowuta,
2 (O)'= e

3. e'= e

4. L* =LL' =L'L E] S_1$ry_er t ! g lo t l o lin _s_

(1 !y_?ft _g-tlpsti o!'s l :
i Mafus for these Questions may vary hom 1 to 2.
5. L.=L++r
6. L'L'=L' 1. Find e-closure of states qo and ql for ths foltowing: 6pil 2012)
7. GMTL = L(MLT 0

8. (L + M)' = (L'M)" = 1l' + t''t)'

Solution
e-closure ofqe = {qe, q1}
Q" e -closure ofql=
ut$l0ll {q1).

2, Describe the languago acceptsd by tho following N.F.A, (Apil 2012)

Solution
6k-e-'@
Language desffibod by NFA is
L = (a a*b*b)
= The set ofall elements which start with a contain any or none a's followed by any or none b's
and ends with b over {a" b}.

3. "DFA may have many final statea", Commont, (October 2012)

Solution
DFA may have many final states: True.
A string can be accepted by FA M = (Q, X,.6, qo, F ), if 6 (qn, x) = q for some q e F. This is
called acceptability of a string by final state or accepting state. A string may reach to any of these
states to get accept€d so many final states are possible.

4. Differentiate botweon Moore and Mealy machine. (April2013)

Solulion
Moore Maehlne l Melav Machino
I Tuple Tuple
M= (O,E,^,6,r,q0) M = (Q, ,, 6, 1", qo)
6: QxE+6 6: Qx, )6^,
l,: QJ A i.:Qxt-+d
ti The oulput is assoc ated with each state Oulput is assoclated with each transition

T.Y, P ll-Theoretical Comnuter Science r @ . Finite Automata &

ut8t0n
 a
o. T,Y. P ll- Theorelical Compuler Science t t Finite Automata
(
T.Y, P ll- Theorctlcal Computer Sclenca a Finite Automata $r0i ullt0i
(October 201 3) 13. What is the significanca of word 'Automata' in FA?
i. Construct NFA with €' transition for a*'
Solution
lolutlon
It is called automata because the change ofstates is totally govemed by the input. It is automatic
not willful just like motion of hands ofa clock but does some predefined task.

'14, State true/false: lf the length of input string is n, then the output gonarated by
e Mooro machine will bo of length n + 't.
a. Write mapping of 6 in case of NFA with e ' Closure' $pil 2014) Solulion
Solutlon True

6:Qx(Xx{e))-+24 15, Justify: Finito automata is a spscial caso of Moore machine,

7. Dofino Moore machine. (stato its tuplos). 6pd 2014) Solution
True. Finite automata is a special case of Moore machine where output alphabet is {0,1} and a
Solution
Moor machine tuples state q is "accepting" ifand only ifl,(q) = 1.

M = (Q, E, A, 6, r, qo) where

0: QxE-+Q Ell ln"-"r the followlng (5 lUlarks Questlons) ;

Mai(s lor tlBse Questions may vary frcm 4 to 5.
7.: Q-+A
l. Construct DFA for a language ovor (a, b) whlch accepts all strings that contain
8. Stato truerfalse: OFA i8 a special case of NFA' sub3tring bb or do not contain tha subslring aa. (Apnl 2012)
Solu{on Solu0on
True Tronsitlon diagram
9. What b the function of finite control of Flnito Automata?
b

Solution b b
one ofthe states as its value'
if," registe, of tf," machine is also called the finite control contains
value of the register is q6 i e stsrt stste of FA'
et t'f," l"iinnirg of computation, the
'
" a

10. What characterigtic makes DFA deterministic? And NFA nondeterministic'

Solution
In DFA, one state on one input symbol transits only to one and only
one state'

In NFA, one state on one inPut symbol may tansit to none or many states'

,l1. ln how many different ways DFA can bo reprosgnted? - M = ({qo q,, qa qr, q4), {c b}, 6, q0, {qr q, q,))
Solution where 6 is
FA can be repres€nted bY 2 waYs - a b
i. state- transition diagram qo q3 ql
ii. Transition table ar q3 az

12. Why FA is called 'Finite'? Ar ar q2

Solution inifq. fq, I

qa qa
It is called as Finite because the numb€r of possible states and number of lette6 in the alphabet ar

are both hnite.

 ( a
T,Y. P ll- Theontlcal Computer Sslence
'
r Finile Automata T,Y. P ll. Theoretical Computer Science a
E I Finite Automata
ullnf
(Apfl 2012) 0
Construct DFA equivalent to given E- NFA
0
I 0 0
0 1

olution
e -closue and transition table
0,1
6
0
0 1 €- closure
0
ao q1 qo {qo, q,}
ql at q, {q,) 1

q2 q3 q2 {q, q3} 3. Minimize the following DFA. 6pfl 2012)

q3 q2 (q3} a
aa a b

Stan $at€ ofNFA = qo.

. . sfft state of DFA = €-closue (qo) a,b

={qnq,}=A
6'(A, 0) = e+losure (6"(A,e), 0) = q = B
6'(A, 1) = (qo, qr, qr, qr) = C
a,b
6'(8, 0) = B
6'(8, l) = {qu, qr} = D
0'(C,0) = {qr q:) = E
a,b
6'(C, 1) = {qr, q1 q3} = F
Solution
6'(D, 0) = {6} =G
a b
6',(D, 1) = D
.6'(E, o) = E
6(E, 1) = D ab
b
.6(F, o) = E ab
a,b
6',(F, 1) = E
6(c, 0) = c Transition table
6'(c, 1) = D a b
Qo Qt Qr
Final state in NFA = q2
ql d 9;
. . Final state in DFA = e - closure (q) q2 qr qa
= (qr qr) qr q5 at
=D. qa Q: Qr
qt q5 q5
 t o ![ . ()
T.Y. P ll- Theoretical Computer Sclencs E i Finite Automata
5.
T.Y. P ll. Thsorctlcalcompucr sclence Flnite Automata

Construct DFA for a languags over {a, b} which accepts all strings that 3tarts
eru0i

a, with 'aa'but not having 'aa'as substring in the further sFing, (October 2012)
q, x x Solution
ql x x x A

q1 X X x x
a a
9s x X x x
qoq,ASqr a

art one flnal and one non final state as 'X''

ql+qoandqr+q{ - qo+qr+q4
a
a,b
b
Iq, q1l lq. qJ a,b 6, Convert following NFA with € - moves to DFA. (Octobar 2012)
0 1

a a,b
s 0

1.<
o,€

(Apfl 2012) Solution

Construct a mealy machine to replace 110 by '101'
,lution NFA with € - moYes to DFA J
Melay machine 1 0 0 1

1t1
s 0
111 0/0

1,€
0,e

0/0 111

6 0 1 € closure
1t1 ql}
qo qr ao qi qo {qo
qJ (qo qd qi o q, (q,
0/0 q, ql
q2 {qo ft} q2 {q2, qo, q1}
q3 q? q3 q, q3 {q3. or, qo, qr}
Transition table
6 ),
Here final state = q2.
0 1 0 1
qj 0 1 Start state in NFA = q6
ql 0 0
1 1 .. start st3te of DFA = € -closure (q0) = {q, q,} = A
qj 0 I
(s 0 1 .'. 6'(A,0) = e-closure (6^(A, €),0)
0 0
= e-closure ({qo, qr}, 0) = e-closure (qr qo qz) = {qo qr qz) = B
6'(,4., 1) = €-closure (6^ (A, e), t) = A
a=r'::--

o" T.Y. P ll- Theoretical Compute. Science r Finite Automata

(
T.Y, P ll- Theoretical Computer Science
. Finite Automata ur5t0i
ut8,0i

6'(B, 0) = e+losure (6"(8, e), 0) = e-closure ({q0 qr

q2}, 0) Minimize the following DFA. (October 2012)
M = ({Qo, qr, qz, qr, 9+ 9s}, {a, b} o,qr (q, q5}) where 6 is given by
= e-closure ({qo, Qr, 9r)) = (qo q, qz} = B
6'(8, 1) = Ealotur" 1{q0, qr, qr}, 1) = ({qo qr qu ft) =C t6T"Ttl
tc;Tq,Ta;-l
' 6'(C, 0) = (qi q1 q) = B Or 0o Qs
q2
6'(c. I )= {qoqr q2 qr)=C Qr Qr
qj 9o Qs
Einal staE ofNFA =
q2
Qr ar q3

.. final states ofq2 = €-closure of(q, Os Qo Qs

={qoqrq2}=B Soluoon
.. Final DFA The table is
00 qj x
c, X

1
1 9r X X x
TTT-' q. X X x x
B B c q5 X X X x X
1 C B c Sqrq,q!q'
0 Mark (final. non-final states) as X
.i Mnk - (q0, q, (qr qr) (qz qr) (qr q) (qo q') (qr q:) (qz qr) (q, q)
Check (qo qr) + mark X
Check (qq q) ma* =
=
gives output .A, if string mark X
construct Mealy machine to accePt strings over (a, b} and Check (qo qr)
=
JJri'i* 'r'"il 6rr!; output'B' if itring contains 'bba' slse gives outPut'c" Check (q1 q) > mark X
(October 2012)
Check (qr qr) + mark X
)lution
Check (qr qa) mark X
Melay machine =
at. Check (qr qs) mark X.
=
. . Minimized DFA
alC alC
a
a tq,q,
b/c alB
b

alB

b
b/B a
 T.Y. P ll. Theoretlcal computer Science r l[ r Finite Automata
(k
urfl0,t
T.Y. P ll- Theoretical Computer Science t r Finite Automata

over {a, b, 4 suchnthatlstring

11. ln how many different ways DFA can be ropresented, explain in detail,
Construct DFA to accept tho set of all strings Solulion
ends with 'bba' or'bac'. The finite automata can be rcpresented by hryo }vaJs viz.
;olution a i. State,transition diagrsm: A graph cofltaining nodes and arcs.
A tronsition diogramfor a FA, M = (Q, Z 6 q6 F) is a graph defned as/ollows:

a,c a. For each state in Q there is a node.

b. For each state q in Q and each inPut symbol a in E, Iet 0(q. a)= p. Then the tsansition
diagram has an arc from node q to node p, labeled a. If there are several inPut symbols
that cause transitions fiom q to p, then the transition diagran can have one arc, labeled
c by the list ofthese symbols.
c. There is an arrow into the start state qo, labeled start. This anow does not originate at
any node.
d. Nodes conesponding to accepting states (those in F) are marked by a double circle.
a,c States not in F haye a single cirole.
Example
,l0, (October 2013) 't 0 0,1
Convert following NFA with € moves to DFA'
a
0 1

Stan
s
The diagram has 3 nodes i.e. 3 states.
a,b qo: Start state (pointed to by 'start' arow)
q;: Final state indicated by double circle.
a,b
a b a,b Each arc represents the transition made on a state q on some input symbol and reaching to
other state.
Solution
q0 contains one arc on input symbol 'l', rcaching to qe is called a self loop.
Transition table and e moves
lt. Transition table: A tabular listing of 6 function which tells us the set of a states and the i/p
a b € closure alphabet.
d
(qo,q1'qr,qo)
9o o
Transition tqble
ar as d iq1)
q2 {qr,qa} 0 {q2, q!} a. lt is a conventional, tabular.repr€*enlgtion ofa function like 6 that takes two argunents
$
qj {q,} arld retums a value.
q5 {q,}
q4
qs {qr,qs}
{or,q5}
{qr,qs} (q5) b. Rows ofa table corie-spond to the states.
c. .tr['olumns ofa table conespond to rhe input symbols
Stan state ofNFA = qo
d. The entry for the row conesPonding to state q and the column coresponding 10 input
.. start state of DFA = e -closure (q0)
'a' is the state 6(q, a).
= {qo,q,,qrqo) = A
e. Start state is marked by '+' (anow).
. . 6'(4, a) = e-closure (6^ (A, e), a)
f. Accepting states are marked by r (star).
= e-closure (qr 9:, 9r, 9:)
= {qr, q+ qr qr} = B
 T.Y. P ll- Theoretical Compubr Scienco .@ a Finite Automata
().
ott 0i
o"
T,Y. P ll- Theoretical Computer Science a t Finite Automata
0llt0i
Exanple
6'(4, b) = e<losure (0" (A, e), b)
Thc transition table conesponding to the function 6 is as shown

--+
N.
9o
0

9z
I
qo qo - start state
= € -closure
= {qn, qr} =
(q4,

c
q,

qr q1 q1 - fnal state 6'@, a) = 6-s1.tu.16^@, e), a)

9r
o^ q, Qt = €-closure {qa q+ qr)
= ({q,, q{. q5)) = D
The FA as a whole is rePresented as
6'(8, b) = 6*1or*.16"@, e), b)
the DFA M = ({qr, qr, qz}, {0, 1}, 6, qo, {q})
= e-closure ({qa, q5, q1}
where 6: 6(
%,
0) +q Transition table
= ({qr, qo qr} = n
0( qo, 1) +% \o\ 0 1
6'(C, a) = e - closure (q+ qs): {qn, qr} = C
6( qr, 0) ,qr qo q2 qo
6'(C, b) = q - r1.rue {qo qs) = {q+ qr} = C
, 6(9,, 1) -+q, o q1
I
,I
6'(D, a) = 6 - closure {q2, qa, q5) = {qaqoqs) = D
6( q,,o) -)q, q2 q2 q1
6'(D, b) = € - closur€ {qa, qj) = C
6( q, 1) +q, 5'(E, a) = 6 - closure (q, qa, q5) = {q,, qr, qr} = E
The transition diagram is 6'(8, b) = e - closure {qn, qr) = C
10 0,1
Final state of NFA = (qr,qr)

stafl 0 . . final DFA=

a
a,b

12. Discuss tho exocution soquance of FA. b

iolution = (A,B,C,D,E)
A computation of an automaton consists of the execution of a sequence of instuctions' b

The execution of an instruction alteN the state of the machine and moves the tspe head one b

square to the right. a b a

L The instruction set is obtained from the tratrsitiotr function ofthe FA,
ii The machine state and the symbol scanned determine the instruction to be executed.
13. Convort following NFA with € moves to DFA, (October 2013)
The objective of a computation of an automaton is to determine the acceptability of the inPut a
string.
/. The computation begins with the tape head, scanning the leftmost square ofthe tape and the s
re8ister containing the state qo.

i. The machine then alters its state as per the instsuction and the tape head moYes to the right a,b

/ii. The instruction cycle is repeated until the tape head scans a blank square, at which time the
a,b
computation terminates. a b a,b

riii. An input string is accepted ifthe computation terminates in an apcepting state Otherwise it
is rejected.
 o T.Y. P ll. Theoretlcal Computer Sclonce . E a FinitoAutomata o
ut8l0i
T.Y, P ll- Theoretical computer Scienco @ t Finite Automata
. . final DFA=
olution
Transition table and € moves a,b
a
a b e closure
b
qo b o {qo,q,qr,q.}
= {A,B,C,D,E}
q1 q3 b {q'}
(qz, qo) b
q2 {q:,qd o -
as s qr {q, b

aa
q5 {tu,q5} (q,)- b a
q5 {qo,qs} {qo,q'} {q'}

Start state ofNFA = qo

. start state ofDFA = e -closure (qo)

14. Construct DFA to accept the set of all strings ending with 'a' and not having
= {qo'qr'qz'qo} = A c}' Pct 2013)
'abc' as a substring ovor, = {a, b,
'. 6(4, a) = €-closure (6"(.4, €), a) Solution
bc a c a
= e-closure (qr, qz, Qo 9)
a b c a
. ={9,9tq,qr}=B
6'(4, b) = e-closure (6"(A, e), b) b,c

(qa, q5) a
= e+losure
= {qo, q5} = c
6'(8, a) = e-closure (6"(8, e), a) b,c

= e-closure {q2, qa, q5)

Transition table
= ({qz, q+ qs)) = D
qo qr
a lb
qo
Eqo

6'(B, b) = e-closure (6"(B' e)' b) qr q1 q2 qo

qz qo qo q3
= e-closure ({qr, 9s gr} q3 ar q3 q3
q{ qs qs
= ({qr, q" qr} = B ar
qs qa qs qs

6'(C, a) = e - closure (qa q5) = {qt qt} = C I (April 2014)

15. Convert following NFA to DFA.
6'(c, b) = € - closure (q+ q:) = (qt qr) = c
a,b ah
6'(D, a) = e - closule (q2, qa, qt) = {qaq"q:} =
D

5'(D, b) = € - closure {qa, q5) = C

6'(E, a) = e - closure {q3, qa, q5) = {q,, qo

qs) = E
b a,€
6'(8, b) = e - closure (q, qs) = C
Final state ofNFA = {qr,qr}
 (h
T.Y. P ll- Theoretical computer science I l$ r Finite Automata ut8t0n

olution
I'u"
ao qo (qo, q, e - closure (qo)= {qo, q1, qr, $)
q1 { o € - closure (q1) = {qr, qr, $} i

92 (qz, q") q2 € - closure (q, = (qr, ft) I r the following ( 1 Mark Ouestion
q3 (qr q,) q2 € - closure (q3) = (q3) l these Questions may vary Imn 1 to2

Stan state ofNFA = qo (April 2012)

1. List the eloments of ths languago described by L = {0+1)'0'
.'. start state ofDFA = € - closue (q0) = {9o 9r, qa q:} = A Solution
6' (A, a) =e - closure (6"(A, e), a) Elements described bY L = (0 + l)r0
= {0,00, 10,000, I10, 100,010, 1010,0100, }
= e - closue {qo, qa qr. q,} = A

6' (A, b; = s - .1.tue {qo, $, q2} = A 2. Find the Regular Exprsssion for the language containing exactly zb's over
rl . ,= {a, b}. (APrit 2012)

Iq",q,,q,,qJ a,b Solution

Regular expression r = a*batbar

3. Prove that l.:L = L'with the holp of suitable exampla' 6p 2012)

Solution
I-et l, = a
@
.. L'= te,a,aa.aaa . )
L*.Lr = Lr !_/ Lr
ut$1011
= le,4aa,aa4...) u (e, a, aa,.. . )
= le,a,a\aat,...)

Hence the prooi

4. Show that the class of regular languages is clossd undor intersection'

(Apil 2012)
i
Solution
To prove this we will apply De-Morgan's Law

L1nL2 = G; uL)'=G+L;)'
i.e., the language L1 L2, consists ofall words that are not in either Li or Li since Lr and L2 are
^
regular sets. Then, Li and Li are also regular.

(),
T.Y, P ll-Theoretical Computer Science a I Regular Languages l,lst0n
 T,Y. P ll.Theoretlcal Computer Science I a Regular Languages
T.Y, P ll-Theoretical Computer Science i Frl I Regular Languages
I
Lj + Lj is also regular, as Li and Li are also regular. 8, State any two oparations on languagEs, (Apfll to'i:J !
Solution
. . (Li + L;)' is rceular.
Operations on languages
'. The class ofregular sets is closed undcr complementation. i. Union
.. Lt n L2 is regular set. ii. Intemection
(u.L;) .

9 Describe in English ths set accepted by the following FA. iAri,t 2i :

0 0 0,1

I
S 1 1

Solution
Construct FA for L = {€}. (October 2012)
rlution The set ofall strings over {0,1} where each string has exactly one
.,1,,
in it.
FAforL=(e} I
10. Write RE for tho set A = (aa, aaaa, aaaaaa....)
Solution
R.E. forA=(aa)",n> 1

Writo the smallest string gsnsrated by regutar expreseion: b(a*b + ab.)c,

(october 2012)
11. Writo.a regular expression for the languags consisting of stri,,s. ..
rution divisible by 3 over {a}. (ectobrr ..,.t
b o c or hbc Solution
smarest string is bac or bbc. r = (aaa)*

Showthat (October 2012)

12. Write the smallest possibls string accepted by following reguiar e.,p,i,..r ,,,
i, regular languages are closod unuer union, ab + (b + aa) b,a.
ii. regular languages are closed,tnder concatsnation. Solution
lution
Lr + L2 means the language ofall words in either L1 or L2. Say regular expressions for L1 and
11 and r2 respectively.
L2
13. Draw DfA for L = {6}.
{f,
Solution
Then, rl + 12 is regular expression for{-1 u L2.
,I DFA fbr l. = {0}
rrr2 is regular expression for L1L2.

rr* is regular expression for L1l.

-'@ @
.. AII thee types ofthese sets of wordi are definable by regular expression and so are themselves 14, State trueffalse: Each regular set can be accepted by a parii,.:. .

regular sets. Solution

True
 (k
T,Y. P ll-Theoretical Computer Sclence tr i Regular Languages
(h
ul$01
T.Y. P ll-Theo.gtical Computer Science l E , Regula. Languages etd0t
'
18:a
Bl
- -f
lnswel the-follgyVlt'g F,ttlqffi-9,ue!ti-o!t-) ! -
M;tus fot tuse auestions may vary fom 4 to 5' a
. (Apfl 2013)
l. Construct FA for RE: ab* (a + b) + ba-'

,olution
. = ab*(a +b)r + ba*
rl'12
rr = ab' (a+b)r 12 = bar

13 rl3
-+- = rto tll
!=ab+ ra = (a+b)r rro=b

17 = a+b
Tt1 a

_,re-,re
r
a

ttz
rro=b

14=a

f2 = floflr

rq=b h=18+19 I

b
h
€
r13: (a + b)* = (r1a * 115)* : 116*

Ql a

r a
e r,
 {rc E o"
T.Y. P ii. i!r;(-r.etical Computer Scienco t r Regular Languages ullt0ll T.Y. P ll-Theoretical Computer Science r E a Regular Languages ()'
ullt0i
2 Show that L = (anbncn) is non-regular using'pumping lemma of regular sets,
(October 2013) T
Solution
Step l: Assume that L is regular. Let n be the number ofstates in finite automaton.
Step 2: Let w = a5'ci in L.
By pumping lemma, we can urite w = xyz with lxyl< n and lyl > 0.
Step 3: Now try to find out ry'z e L.
There are few oases by which we can split string into x, y and z.
Cqse l; x=c
y=a
z= bnao

w = abnan such that xyiz e L

I
buti+ n.'.xyizeL.
This is a contradiction.

{ Case 2: x= an

v=b"

xy'z = a\b)i a" ..lbl>asi>l

,.. xyiz e L
This is contadiction
Case 3: x= {b'
Y=ao
z= E :.i.Xt.,..1i,1!
:i $
.. w = a"b"d as xy'z is ah'(e)'., r ,

Thus for any value of i, w will not generate valid words.

xyzeL.
This is a contradiction.
Case I
y=aba

... , = laba)i
Fori=lw=abaeL.
For i- = 2w = abaaba e L.

)
 r
(
T.Y, P ll-Theoretical Computer Science t F;l Regular Languages ullr0

Thus we get contradiction'

Ttrough case 1 to 4 we can say that
L is not rcgular.

' Construct melay machine that outputs'V'for valid' or 'l'invalid' for a language
(A1ril 2014)
L = a(a + b) 'b. E Ansurer t rk Questions) :
,lution Ma*s for these Questkns nay vary frcm 1 to 2.
,|
L=a(a+b)'b Construction Regular Grammar, G, for following automaton, 6pil 2012)
b,1 a b
I
b
all

brl a

Solutlon
all btl
S-rAslbBla
Transition table
B-rbBle
9o
qi
9r
q1
a,
qj
9o
2, State what is nullable symbol? (April 2012)
er
Solution
9z ar qi q?

ag 9e q3 ar
In a given CFG, a nonterminal N is nullable ii
a. There is a production N -+ e or,

State the steps how pumping lemma is applied, b. There is a derivation that starts at N and leads to e. i.e. N I e
,lution G
given
Pumping lemma is used to prove that ceftain sets are not regular' The steps required for the The nullable symbols are dangerous as they lead to e-productions
I is not regular as follows:
. Assume L is regular. Let n be the nwnber ofstates in FA which accepts L' 3. Define ambiguous grammar. (October 2012)
Solution
Choose a string w such that lwl > n, using pumping lemma, write w = xyz with lxyl < n
A CFG is called ambiguous if for at least one word in the language that it generates there are two
and lyl > 0.
possible derivations ofthe word that conespond to differcnt syntax hees.
. Here you must picked finite integer as'n', the constant mentioned in the pumping lemma' i
Find suitable integer i such that xy'z e L. 4. What is the yield of following derivation tree? (Qctober 2012)
It may then be concluded that L is not regular, so it contadicts th€ assumption we have made I

in step l.
Hence L is not regular.
-,,1\

o,
utsl0lt
t'
Y, \\O

T.Y. P ll.Theoretical Compuler Science r E a Context Free Grammar and Languages

!f.rh
T.Y, P ll.Theoretical Computer Science t @ a Context Free Grammar and Languages r* T.Y. P ll-Theoretical computer Sclencs a E r conlext Free Grammar and Languages !A
lution 10. Define null production, (Apfl 2014)
Yield ofderivation kee is - abbb. Solution
The production A + e is called as null production.
Define Left Llnear Grammar, $pil 2013)
lution 11. Construct CFG for L = {ambnc*"/m > 1,m > n). 6pfl 2014)
The non-temiinal symbol appears as a lellmost symbol. in each production is called
left linear Solution
tmmw. Example, A -+ Bc lc le L=(a'b"c*'lm>l,m>n)
Language set = {ac, aabc, aaabcc ... ... ... }
Find nullable symbols in ths following cFG. 6pil 2013)
The language is not context free language so NO CFG can be constructed.
S+ABlaBb
A-+aAle 12, What is the ditference between the notations - 3 and ; ?
B-+ADlaAb GG
D-+bDle Solution
'lution I
AsA+ € .. A is nullable
+ Means dircctly derives and means derives.
GG
D -r E .. D is nullable
A and D are nullable symbols. 13. Why Type 1 gfammaE are context ssnsitive?
Solution
Dofine right linear and left linear grammar. (October 2013)
Be.ause the production ofthe form o1Ao,2 -+ orpd2, with p + E, where the replacemeni ofsome
,lution non-lerminal symbol A is allowed by p only in the context cr preceding A and o.2 succeeds A.'
ght Linear Gramnar
-A
regular gnmmar in which a non-terminal symbol appears as a fight most symbol in each 14. State true/falso: Null string can never bo generatad by a CSL.
rduction, Solution
Exanple, A -+ Bal Ab True
:ft Linear Grammar
A regular grammar in which a non-terminal symbol appears as a leftmost symbol in each 15. State true / false: Evory contsxt-free language contains a null string is context
Jd]uction. Exqmple, A --) aB 1 bB sensitive.
Solution
State any ono lemma used in the procedure for constructing GNF'
False
(October 2013)
,lution 16. Every contsxt-sensitive language is recursive' : Justify
)[tent Sensitive Lemma Solution
IfA --r py is a production, where A and B are NTS and there arc B productions ofthe form: I True. L is a context-sensitive iffL (e) is accepted by a Linear Bounded Automaton'
B r Brl0,1... Ps then 17. Type 0 grammars are called Semi Tune grammars'
We can replace the production A -+ py by A -+ p l where 1< i< s. I Solution

Define Chomsky Normal Form' $pril2014) True

rlution 18. Define Parse Tree.

A contcxt lree grammar is said to be in Chomsky notmal form (CNF) if and only if every rule is
Solution
the following forms
A +albrsomeAeNTandaeT Let G = (V, E, P, S) be a CFG. A tree is a derivation (Parse) tree for G ii
A+BClorsomeA,B,CcNT i. Every vertex has a label, which is a symbol ofV r...r T u {e)
. S+e ii. The label ofthe rcot is S.
 T.Y. P ll-Theoretlcal Computer sclence . g r Conlext Fres Grammar and Languages
u*
T,Y. P ll.Theoretical Computer Science t l;;I t Context Free Gtammar and Lanquages o
Lll. Ifa vertex is interior and has label A, then A must be in V. F-+aFla
Ifn has label A and vedices n1, nr, . . . nr are the sons of vertex n, in order from the left, with 'F' is nol reachable tom start symbol eliminating
labels xt, x2, . . , xr respectively, then A -+x! x2... x1 Final grammar is
must be a Production in P, S+aA
If vertex n has label E. then n is a leafand is the only son of its father. AeaAlaD
D-+bDlb
19. Stato the rules to deal with associativity whils constructing the parse tree,
sblution 2. Convert the following grammar to CNF
6pil 2012)
Rule I: Ifthe operator is lefi associalive we add the left recursive Produclion in the grammar. G:S -rAlC
Rulc II: tf the operatot is right associative, we add the right rccursive pro&rction in lhe g"mmar. A+aAlalB
B-+bBlb
EI Answe. the followin 9 (5 Marks Questions) :
CrcClclB.
Solution
I Ma*s lor tlr,se Questions nay vary hom 4 to 5.
Removing unit productions
l. Construct tho equivalent grammar by eliminating useless and non-reachabls
symbols. (Apfl 2012) s-;aAlalbBlblcClc
G:S-raAlBD A-+aAlalbBlb
A-+aAlaABlaD B-+bBlb
B-+aBlaClBF
c-+BblaAClE C-rcClclbBlb
D-+bDlbClb Let C,, a, Cb + b substituting in grammar
E-+aBlbC .. S -+ C"A la lC6B I b iC"C c
F+AFlaGla I

G-+alb A -+ C"A a lC6Bl b

Solution B+CbBlb
E - symbol
does not yield terminal . . eliminating C -+cC lct CbB lb
G: is not reachable ftom start symbol . . eliminating All above productions in CNF.
Rewriting grammar
S +aAIBD
3. Convort the following grammar to GNF (Apnt 2012)
S-+BB
A-+aAlaABlaD
'B+aBlaclBF A-+AAla
B-+AAlBAlb
C+BblaAC
Solution
D+bDlbCib
Grammar is already in CNF.
FiaFla Lets replace S by Ar, A by 42 and B by 43.
'B' and 'C' are not reduceble to terminal symbol .. eliminating.
.. Ar + A3A3
lewriting grammar
42+A2A2la
S)aA
A -+aA aD
Ar , A2Ar l AjA, b

D+bD b ConsiderAl +A3A3 i<j . . leave production

 T.Y. P ll-Theoretical Computerscience I E r Conlext Free Grammar and Languages r(L
T.Y. P ll.Theoretical Computer Science I
Let Lr is a language containing equal number ofa,s and b,s.
n r Context Free Grammar and Languages
ur!,

Consider A2 -+ A2A2 | a .. ACFG Cr.= ({sr}, {ab),P1,51})

immediate left recwsion occurs
P1 = {S1 -+ aS1 b lab}
le,- u ,p,l i, in cuP. Let L2 is a language generated by grammar G: = (tSz), {a. b, c}. p:, Sr)

Br -r AzlAz0r where, Lr= {wo/lw e (a+b)'}

Substitute A, in Pr Now we take the union ofLl v L2 and grammar G for union is:
0r -+ a la0r la0r0r is in GNF. G for union is:

Consider Ar -+ AuA: I ArAr I b SrSrlS,

Substitute A2 in 43 51 -+aS1 blab
43 -+ aArl ap 1A.,I Ay', Ib 52-+aSralbS2blC
removing immediate left recursion From this we can see that
Ar -+ Azl aA:Dzl aFrAzPzlb9z
All strings which derive from S -+ 51 are in L1 and a.ll strings which derive from S -+ 52 are in L2.
02 -+ A2 | ArP2
All strings from both the languages are derived from S. And we get the union of two languages
_ ...
Substitute A, in Al and P, which is CFL.
Ar -r a I aBrl aAz9z la0 rA#z is in GNF Moreover, as we can represent CFG for
lb0z L = Lt w h, the grammar is context frce and the
0z -r a I aPr la0zlaPrPz
language generated by it (L) is also a CFL.

Substituting A3 in Ar Hence, we can say that, CFL'S arc closed under union.

-) is in GNF 5, Construct CFG for L = Lr v Lz. (October 2Ol2)

Where Lr = (anb/n > 1) and L, = {0"i"/n > 1}.
AII productions are in GNF. Solution
Replacing ,A1 by S, Az by A and Ar by B, 0r by C and 0z by D Lr=LruL2
S -+ aBlaCBlaADBlaCADBiBdb L1 = {a%/n> ll h = {0"t^/n > l)
A-+aC L1= {ab, aab, aaab....} Lr= (0"1"/n> l}
B -+ alaClaBDlaCBDlbD L, = {01, 0011, 000111....}
C -+ alaClaCC
D -+ alaclaDlacD
S1 )ab
is final grammar S1 + aS1 G2: 52 -+ 0l
Sr + 0Szl
l. Show that CFL'9 are closed under union. (April 2012, Ocotber 2013)
L=L1vL2
;olution
oroof
= LrLz
lfLl is a CFL, then it is generated by grammar Gr = (Vr, tr, Pr, Sr)
S=S152
lfl2 is a CFL, then it is generated by grammar Gz = (Vz, I:, Pz, Sz)
31 -+ aS1 lab
We havo to show L = Ll u L2.
sr=osrll0l
Let L be generat€d by a grammar G,

c=(vr u V, u (S), tl u ,r, P, S)

 T.Y, P ll"Theoretical Computer Science a @ r Context Free Grammar and Languages rrL T.Y, P ll.Theoretieal Computer Science I I Context Free Grammar and Languageg a
qamn

6. Rewrite following CFG after eliminating unit productions' (October 2012) Substituting A2 in Ar and Al
S -) aAblA -)
A -+ Blb
-+ bA b
B+e
. D-+F Substituting 42, Ar in pr
F -+ 01lB p' + blbprl bAjArbprArArlaArbprlbprprlbAlA, DrlbprArA, 0rlaA2pr
Solution . . whole grammar is
' S+ A-+€ Ar)bArlbprA3
A J B-+ € substituting ftmction
Ar-+ blbpl
SrA *A+bl€ 41 -+ bAslbpl43la
.. S -r aAblble p1 -+ bibplibAy',lbplArA, aArlbgriborprlbAdrorlborAdzprlaAzpr
A -+ elb After resubstituting A1, 42, A1 by S, A, B respectively.
D + F and F + 01lB are eliminated as D and F is non reachable from stad symbol'
S --r bBlbp 1B
.. final productions are:
A -+ blbpr
S-+aAblb e
B -+ bBlbplBla
A-relb p1-+ b bpllbBA bplBA aBl bpllbplpllbBA p1b0 rBADrlaBpr
7, convert following grammar to GNF' (October 2012)
S-+AB 8, Construct CFQ fqr L = {arbvcz I x>y+z} , (Apfl 2013)
s -+ AAlsAlb Solutlon
B -r ABla The language set
Solution
L = la, aab, aac, aaabc, aaabb, aaacc, aaaabbc, aaa
The grammar is already in CNF.
To generate shings ofa* when y = 2 = I
Replacing S by Ar
S --r aAla
AbyA,
A e aAla
. BbyA3
A1 -+ A2A3
Whenz=0 wheny=0

A, .) A2A2 lArArb SraA S-+aA

' A, ,ArAr,. A -+BAc A -r Cab

41 -+ 42 A2 leave i <.j B r cBlc C --r bclb

A, + A, 42 iArA, b substituting Ar production Whenzandy>0
A2 + A2 A2|A2A3A,lb . . Final grammar is
Removing immediate left recursion S --r aAla

A, r bl bBl A + aAla
B -+ cBlc
0r + ArArArA20 rlArA,0 |
C + bclb
 T,Y, P ll-Theoretlcal Compuler Sclonce t a context Free Grammar and Languages i#.
(Apfl 2013)
T.Y. P ll-Theoretical Computer Sclence a I Context Free Grammar and Languages .*
9. Rewrite following CFG after eliminating useless sym bols.
0r --r &lAzPr
S -+ 0Ai/BD
A -r 0AA/011 Consider production Ar 9 ArArlb 2< 3 .. leave production

B -+ 081/80 g -+ A2A2la 3> 2

D-rA0 . . Substitute A2 in A1
E -+ 1D/0
Ar -r Ad:Au lbA., ia
Solution
Removing immediate left recursion
i. NT 'E' is not reachable ftom start symbol
Ar + b&la bAz0zla0z
.. it is useless.
-+ lvAzlAzAzqz
Production E -+ lDld
Fz
.. we remove
Substituting 43, in A2 production
ii. NT 'B' is not getting derived to teminal symbol in the grammar

.. it is useless. --)

. . We remove 'B' productions from the grammar Substitute A.2 in pr and p2.

S-+BD pr = bArArlaArlbAr0rArlagzA:lblbArAr0rlaAzgrlbA:0rAuFrla0rAzPrlb9r
B-+0BllB0 A:Fzl
gz= bA:ArArlaAzAzlbAzgz&Arla0z&AzlbAzlbAzAzArPrlaAzA:0zlbAz0zAz
iii. With this NT'D' is unreachable from start symbols
aFzAzAz0rlbAzPu
.. it is useless
.. we remove D -+ A0 Resubstituting S, A, B values for A1 42 43 respectively the final gammar becomes:

. . Final set ofproductions S -+ ala9r

S -+ 0A1 A -+ bAA laA lbAPrAla0zAib

A -+ 0AAl01 l. B -r bA a'bA9z a0r
(Aprit2013) 0r -+ bAA laA lbADzA laPrA lblbAAPr aADrlbAPzAgr laPrA0rlbDr
10. Convert the following grammar to GNF'
S -+ SAla pz-+ bAAAIaAA lbApzAA laFzAAlbAlbAAAp, laAAPrbAprAApdaPrAAPzlbAPz

A -+ BAlb (Aprit2013)
11. Minimizo tho following DFA
B -r AAla M = ({qo, qr, qr, er, 9o 9s}, { 0, 1 where 6 is given by
Solution 6 0 1

Replace S bY Ar 9o 9r 9o

AbYA2 9t 9e 9s
Qz Qs 9r
BbY43 9r
9r 9r
Ar + ArAra 9r 9s 9t
Qs 0r Qr
A2 + ArArb
Solution
A3 + A2 Ara 9, X
q, x
Consider production Ar -+ ArAzla
9: X x X
Removing immediate Ieft recunion qr x X
q5 x X x X
) ftq,q,ftq.
 T,Y. P ll-Theoretical Conputer Sclence . @l a Context Free Grammar and Languages ,# T,Y, P ll.Theoretical Compuler Science I t Context Free Grammar and Languag$
ia
Mark 'X' - one final and one non-final slate Y=ryzlb
.: Mark (qo q) (qr qr) (q, q,) (qo, qr) Z-+aldle
(qo q,) (q, qr) (qr qr) (q,, q) Removing e production
Mark (qr qo), (qo q) as 'X' X --| axbdz I aXbYdZ

The states (qr= qr, (q1= q); and (qri q) Y )XZlblxYZ

Z-+ ald
.i (qr; q, + q, and (qr + q,
JA Y )bXZ are already in CNF.

Y +XYZ -t let XY + Yl
(qr q: qJ '.Y )Y&
0,1 is in CNF.
Yi -+ XY
0
-+ )b )
.. X-rA1 aA2A3ZIAtXA2Y AtZ
(q,, qJ
Let Xr + ArX, Xi-) A3 Z, X3 --rA2 Y
.'. X r Xr 42 Xr lXr X2 X3
0
Let & -+ Xr A2 .. X -) Xa X3lX5 X3
12, Construct CFG for the following languages: (October 2013)
X5 -+ X1 X2
i. L={a"b'c'lm > 0, n >'l}.
. . Final CNF
ii. L=(w6vRlw€ (a+b) *). X+XaXr lX5 Xr
Solutlon
Y -+YtZlxzlb
L{aabcc,aabbcc,....}
Z-+ald
Terminal string is aacc. -r S -+ aacc Y+XY
To generate multipte (aa)'(cc)* -+S --r aaScc Xr +ArX
To generate string like aab*cc -+ S*r aaAcc and A x2-> A1z
-r bA I b
ijo the final CFG is - Xr-+A2Y Ar)a
c = ({S,A}, {a,b,c}, P, S)
Xa-+X1 42 A2+b
X5+X1X2 43-)d
Where P is:
L

S + aascc I aaAcc aacc 14. Construct FA for the following regular grammar. (October 2013)
A-+bAlb S-+aAlbB
A-+aSla
13. Convert th6 following CFG to the equivalent CNF. (October 2013)
I B-+bSlb
X-+aXbYdZ
Solution
Y+XYZlb Construct a finite automata coresponding to following grammar:
Z-+aldle S-+aA bB
Solution A-+aS a
X + aXbYdZ B+bSlb
 T.Y. P ll-Theoretlcal Compute, Scienc€ a @ a Context Free Grammar and Languages
!fi T.Y. P ll-Theoretical Computer Science r 4-15 t Context Free Grammar and Languages

The finite automata accepting the language generated by above grammar will be 16. State and prove union and closure property for CFL. (April 2014)
M = ({qo qr, qz, qr}, {a, b},6, qq, {qr)) Solution
where, q6 conesponds to S : start state IfLr and Iz are CFLS, then there union is also a CFL,
ql coresponds to A, q2 corresponds to B
IlLr is a CFL, then it is generated by grammar Gr = (Vr, ,r, Pr, Sr)
qfnew final state
5 can be defined as: If Iz is a CFL, then it is genemted by gmmmar G2 = ry2, 12, Pr, S,
Production Corresponding transition We have to show L = Lr v Lz.
SraA 6(qe,a)-+q1 Let L b€ generated by a grammar G,
S --t bB 6 (qe, b) -+ qr
A -+ aS 6 (q1, a) -+ q6
G=(V,u%u{S},Lut,P,S)
)
A+a 6(q1,a)-+q1 Let L1 is a language containing equal number ofa's and b's.
B+bS 6(qr,b) -+ Qo .. A CFC Gr = ({Sr), {a, b}, Pr, Sr))
B+b 6(qz,b)-+qr
Pr = {Sr -+ aSr b I ab}
.. The conesponding FA willbe:
a Let L2 is a language generated by gammar Gz = ({Sz}, {a, b, c), Pz, Sr)

a where, Ia= {wcwRlw € (a+b)'}

Now we take the union ofLl v L2 and grammar G for ulion is:

G for union is:

b
b S-+51 l52
Sr+aSrb ab
15. Show that the following CFG is ambiguoua. (October 2013)
Sz-raSzalbSzb C
S-+aBlaA
From this we can see that
A+aABlalb
All strings which derive from S -, Sr are in L1 and all strings which derive from S -+ 52 are in L2.
B+Abblb
Solution
.. All strings from both the languages are derived from S. And we 8et the union oftwo languages
which is CFL.
Consider a string aaaaabbb to parse the string using above grammar we get two differcnt parse
trees as shown below so the grammar is ambiguous.
Moreova, as we can represent CFG for L = L1 v L2, the $ammar is context free and the
(L) is also a CFL.
language generated by it

aB
,z'\ ,z'\
aB aA lt
Hence, we can say that,
CFL'S are closed under union.

lt CFL'S are closed under kleene closure.

Abb b aAB b
I I l
Let language L be generated by grammar G. Suppose the grammar has only one production
x x -+ a and hence the languagE generated by it consists olonly 'a'.
S
aAB a b aAB ib
Now if we want the language having all the strings in a', we generate a granmar as S -r aS I e.

aAB ab
,/\\ I I
JA Here we are applying productions repeatedly in derivation, to get closure.
Abb b
/A\ xr
a/ I
x So the word in L' represented by CFG.
Ab bb abb

I
.. We can say that CFL'S are closed under kleene closure.
abb
 a Context Free Grammarand Languages r* T,Y, P ll.Theoretical Computer Science a
IE r Context Free Grammar and Languages
.fi
T.Y. P ll-Theoretical Computer Science
' lE
17. Convort lollowing grammar into GNF'
(Apfl 2014) 18, Explain in detail the differenco b€tween the notations - +and l? a
GG
S+AB Solution
A -r BSld ,
+ directly derives and > means derives.
, B+ASlh
Solution IfA -r p is a Production ol P and o and y are any string in [V u T)', then
Replace S bY Ar, A bY A, and B bY A1
oAy + apy.
' .. Grammar b,ecomes c
A.1 -+ 42 43 We say that the Production A -+ p is applied to the string cA1 to obtain o.Py or oA1 directly
A'z+ArArla derives uP1 in grammar G.

Ar -+ Az Ar lb Two strings are related by (or +) exactly wher the second is obtained from the first by one
= G
Consider A1 A1
+ A2 1 <2 leave
application of some Production.
Az -+ArAr 2<3 leave
+ (derives)
A3+A2A1 2>3 G

. . Substitute A2 in Ar Production Suppose al, ct2, ...., o. ) I and

are strings in (V u !)r, m
Ar+ArArAr1b
=GGC +Ot,.... -I+qr.
Ot (t2,02
Removing immediate Ieft recunion
t*
is in CNF Then we say that ol + on or ot derives o., in grammar G. i.e. + is the reflexive and transitive
GG
p+Ar Ar0 ArAr closure.

Substituting Ar in A, Production o =.:p if p lollows from o by application of zero or more Production of P,

G
+bA b a is in (iNIr
b ct -c[ for each string Cl.
G
Substituting 42 in 41
C II cr derives p by exactly i steps, w" ruy o5 p.
JbA b is in GNF

Substituting Ar in 0 19, Explain two methods to construct FA from regular grammar.

+bA b bA is in GNF Solutions

Replacing 41 by S, A, bY A and Al bY B Method l: Used when production is A + a B

S+bsBlbPSB
Let G = ({Ao A,, .... A"), L p, Ae} be a regular right linear gnmmar
The finite automata is constructed as:
A-+bSlbPSla
M= (Q, L 6, qo, F) where
B-+blb0
P -r bsBSP IbPSBSB IbSBS bPSBS Q = Number of states conespoDds to number ofnon-terminals.

is the final grammar in GNF. ! = Number of input alphabets is sarne as number of terminals.

qo = Initial/ start state coresponds to the start symbol ofgrammar (A).

6= Transitions conesponds to productions P.
 T.Y, P ll-Theorethal Computer Science a @ a Context Free Grammarand Languages rfir
F= In any derivation thete is the productior of the fonn A1 -+ a which is a
termination production, the conesponding tansition terminates at a new
state and this is a unique final st te.

Then 6 is defined as:

Answer the following { I Mark Questions) I
i. Ifwe have a production Ai + a4 then include the transition 6 (q;, a) -+ q;.
Mafus for these Questbns finy vary fnn 1 to 2
ii. lfwe have a production Ar -+ a then include the fiansition 5 (qr, a) -+ qn

Method 2: Used when production is A -+ a B. l Slate }vhich machines are used for type 1 and typo 2 grammar? wfl2012)
Let G = (V, X, P, S) be a regular grammar then its equivalent FA with €-hansitions Solution
is: Machine used for type 1 grammal 3 Linear bounded automata.

M=(Q.I.6.tsl. ttsl)) Machine used for tlpe 2 grammar a Push down automata.

where, Q is aset ofall productions rules piessnt atLHS as well as RHS. 2. State True/False: Power of PDA and NPDA i3 difterent. fipfl 2012)

I is a set of i,P alphabets * terminal symbols in grammar' Solution

True
[S] is start state + stad symbol ofgramrnar.

{[E]] is the only final state.

3. Write a mapping of 6 in PDA. (October 2012)
Solution
6 is defined as:
Mapping of PDA
i. IfA e V and A -r a is a production then we add 6: Mapping from Q x (X u {e}) x f to finite subsets ofQ x f*.
6 ([A]. e) --+ o.
4. Defino lD for PDA. (APril2013)
ii. Ifa e I and a e (I* u I+ V) then we add Solution
E ([ao], a) -+ [ct] In FA, ID is defined as cunent state of FSM at any time and the remaining i/p string to be
processed to desffibe the finite stale machine.
as we have stach we need to specify the cunent stdte, remaining i/p sting to be
In PDA,
processed and the symbols on the pushdown stack.
,. If M = (Q, r, f, 0, qo, a, F) is a PDA, then ar ID is (q, x,rcr) where q e Q, x e Xl and o e

r+.
i.e., q is cun€nt state.
w is input left to read.

o, IfM
o is on stack (fi$t symbol ofo is top of stack).
= (Q, X, f,6, qr, Ze, F) is a PDA, we say (q, aw, Za) f- (p, w, po,)

ut$t0ll if6(q, a, Z) contains (p, p) a may be e or an i/p symbol.

i.e., If we have a transition O(qr, 0, G) -> (91, BG) then
(q, 011, GGR) f-
(q1,1l, BGGR).

T.Y. P ll.Thsoretical Computer Science I E r Pushdown Automat, o"

5Usr
 r (). r a).
T.Y, P ll.Theoretical Computer Sciencg F;l a Pushdown Automata ur8t0i
T.Y, P ll.Theoretical Compuler Science 0 Pushdown Automata
ut00t

5. State two methods fordefining language accepted by PDA. (October 2013) 12, What are compatible transitions?
Solution Solution

i. The languages accepted by final state by some PDA. Two transitions [q, C] e 6(qi, u, A) and [q6 D] e 6(q1, v, B) are called compatible if any of the
lollowing conditions are satisfi ed:
ii. The languages accepted by empty stack by some PDA.
i. u=v and A=B
6. Tho clasg of languages accopted by DPDA and NPDA is same, Justify truo or ii. u=v and A=eorB=e
false. (October 2013) iii. A=Band u=eorv-e
' Solution iv. u=r orv=E and A=e or B=e
False, there is some class of languages which are not accepted by any DPDA but arc accePted by Compatible traDsitions can be applied to the same machine configurations.
NPDA as shown below.
13. State true / false: A PDA is detorministic if it doas not contain distinct
compatiblo transitions,
Solution
Languages accepled
by NFftDFA True

Ei An.rr., the following ( 5 Marks Questions) r

Languages accepted Malks for lheso Questions may vary frcn 4 to 5.
by NPoA

1, Prove with guitable sxamplo DPDA and NPDA ars not equivalent' 6pfl 2012)
7. State True/Falss: Power of PDA and NPDA is different. Apil 2014)
Solution
Solution
True
i. For finite Automata, the deterministic and nondeteministic models were equivalent with
resp€ct to the languages accepted.
8. State true/fals6: FA accopt every CFL.
The same is not true for PDA. There is some class of languages which are not accepted by any
Solution
DPDA but are ac.epted by NPDA. As shown below.
False
9. State the difforence between 'acceptance by final state' and 'acceptance by accepted by
empty stack'.
- Solution accepted by

Acceplance by final state: PDA accepts its input by consuming it and entering an accepting state. Languages
We call this approach "acceptance by final state". accepled by
' Acceptance by empty stack: The set of strings that cause the PDA to empty its stack, starting
NFA or DFA

from initial ID.

10. State True/ false: For a given PDA P, the languages that P accept by final state DPDA is a special case ofNPDA. NPDA and DPDA rre trot equivalent.
and by empty stack are usually same. The languages accf,pted by deteministic pushdown automata include all regular languages
Solution and are a proper subset of the context fiee languages. This family of languages, which is
False important for Fogramming language definition and parsing, consists ofthe languages that car
11. When do vve call a PDA is deterministic? be generated by LR(k) grammars.

Solution i.e., DPDA's accept a class of languages that is between regular languages and the CFLs.
A PDA is deterministic ifthere is at most one tmnsition that is acceptable fbr each combination ol The languages accepted by NPDA, include all the languages which are actepted by DPDA
state, input symbol and stack top. and which are not accepted by DPDA. i.e., all the context free languages.
 o.
T,Y, P ll-Theoretical Computer Science t r Pushdown Automata ullt0t T.Y, P ll-Theoretical Computer Sclence a
l-,;l a Pushdown Automatr
slel
a
Example, 5 (q, c, R) = 6(q3, R)

LetL= {wwR/we {0, 1)*) 6 (q, e, R) = accept

been reached and make
lnthis emnple,the PDA may decide that the middle ofthe i/p sting has 6 (qe, b, R) = enor
the symbols and tdes to match the
tfr, ,."orO choice: PDA go., to th. state; lryhere we POP 6 (qn, c, R) = enor
iirdrirg yp tyrmfs with-the contents of the stack'
will 3. Convert CFG to PDA (October 2012)
th€ inPut is of the from * nI, then inputs will match' M
empty
If PDA guesses righ! and if S -+ aAb I aBB
its stack anitus accfot the input string. We push 'B' for '0' and 'G' for 1' A+aAbbla
The PDA M is {{q'qr},{0. l}. {&B'G},6,q,R0) B-+aBblb
Solutlon
where, 6 is
S -+ aAblaBB
6(q!, o, R) (qr, BR) -+ BB)}
I
Push B for 0 and G for I
6 (qo, a, S) {(qo, Ab) (qo,
11. 6(qr, l, R) (qr, GR) A-raAbbla
1ll. 6(qr, o, B) {(cr, BB), Decision making whetler to push B for 6 (qe, a, A) -+ {(q6 Abb), (q6e)}
(q, t)) 0 or POP when TOS is B B-+aBblb
6 (q6, a, B) -; {(q6 Bb))
o(qr, o, G) (qr, BG) Push B when TOS is G
6 (qo, b, B) -) {(qo, €)}
6(q1, 1, B) (q,' GB) , Push G when TOS is B
. . final PDA is
6(qr, l, G) {(qr, GG) Decision making whether to push G for 6 (qe, a, S) -+ {(qr, Ab) (qr, BB)}
(qz, e)) I or POP when TOS is G. 6 (qo, a, A) -r {(q6 Abb),(qr, e)}

6 (qo, a, B) -+ {(ql), Bb)}

vll 6(qz, o, B) (qr, e)
POP for all a's and b's 6 (q,, b, B) -+ {(qr, e)}
vlll 6(qz, l, G) (qr, e)

lx. 6(qr, €, R) (qr, s) acceptance by empty stack. 4. Construct PDA fel l = {6nbcm/n, m > {, n < m}. 6pil 2013)
Solutlon
x. 6(q,, e, R) (q" e)
Language set L = {abcc, aabccc, aaabccccc)
(October 2012) 6 (qe, b, R) = enor
2. Construct PDA for L = (a'bmck/ n, m, k > 1, n < m),
6 (q6, c, R) = enor
Solution
6 (qs, a, R) = (q6, BR)
,O41or 1 = 1a" b' ct/ n, m, k > l,n<m)
(qc BB)
1= {abbc, abbcc, abbbc, aabbc
... . }
6 (qo, a. B) --

6 (qo. b. B) - (qr. B)
6 (qo, a, R) = (qo,BR)
6 (qr, b, B) = enor
6 (q6 a, B) = (qq, BB)
6 (q1, a, B) = enor
6 (qo, b, B) (qr, e)
= 6 (q1, c, B) = (q, e)
S (qr, b, B) = (qr, €)
6 (q1, c, R) = (qr, R)
6 (q1, b, R) = (q,, R)
6 (qr, c, R) = (qr, R)
6 (qz, b, R) = enor
6 (q2, e, R) = accept
6 (qr, c, R) = enor
6 (qz, c, R) = 6(qr, R)

I
 0" th
T.Y, P ll-Theoretical Computer Science I . Pushdown Automata T.Y. P ll-Theoretical Computer Science I E a Pushdown Aulomata
utst0i

), Oesign a PDA which accepts a language L = {a"b2"f

n>1). (October 2013) rhe PDA M is <{c' q,}, {0, 1}, {& s, c},6, q, R,0)
6is
tolution
Language set = {abb, aabbbb, } l. 6(qr, o, R) (qr, BR)
Push B for 0 and G for I
II 6(q1, 1, R) (qr, cR)
Logic
t. Push 'B' for €ach 'a'. lll. 6(q,, 0, B) {(qr, BB), Decision making whetlrer to push B for
ii. Read 'b' don't take any action on stack (qz, e)) 0 or POP when TOS is B

iii Read 2d 'b' pop stack. (q,, BG) -) Push B when TOS is G
6(qr, o, G)
iv Rep€at 2 and 3 for,all b's 6(qr, I, B) (qr, cB) -) Push G when TOS is B
Let the PDA M = Qt, a:) a, b) {R, B 6, RO) 6(q1, 1, c) {(e,, cc; Decision making whether to push G for
6(qo, s, R) -) ERROR (qa e))
) I or POP when TOS is G.
can't start with b or e
6(qo, b, R) ERROR vll. 6(qr, o, B) (q:, e)
POP for all a's and b's
6(qo, a, R) ) (q,), BR) vIl 6(qr, I, G) (qz, e) )
Push B for all a's lx. 0(qr, e, R) (qr. e)
6(qq, a, B) -) (qo, BB)
Acceptance by empty stack.
x 6(qr, e, R) (qz, e)
6(qo, e, B) J ERROR ) if No 'b' after a.

6(qb b, B) (qr, B) Accessible ID's for the above PDA when yp is 001100
Read I't b. No change in stack.
6(qr, b, B) ) (qa e)
Read 2d b, PoP (q1, 01100, R) --+ (qr, 01100,8) --+ Reject
6(qz, b, B) (qr,B)
I
6(qr, s, B) ERROR -) After reading l'r b, string ends. (qj,01100, BR)
6(q1, a, B)
qqr, t, R'l |
-,
-
ERROR
(qr, s)
After reading le b, 'a' aPPears.
Empty stack; accePt
I\
(q1, 1100, 8BR) (q?,'1100, R) ---t (qr, 1100,8) --+ Rejecl
6(q1, e, R) ERROR ) After reading l'i b, string ends.
o(qz, e, B) ) ERROR J No. ofa's # (no ofb's)
12 I
(ql, 100, GBBR)

6.
6(qr, b, R)

Explain NPDA with an

) ERROR

examPl6.
J No. ofb's don't match
(Apil 2014) (q,,00,
I\
GGBBR) (q,,00, BBR
Solution
A PDA M = (Q, t, l,6, qe, ft F) is deterministic if
Z'in F, whenever 6(q, e, Z) is non-empty, then 6(q, a, Z) is empty
for all a (q,, 0,
II
BGGBBR) (q,, 0, BR) ---t (qr, s, R) ---+ (qr,6, €)
i:
ii.
nor each
in !.
i
For no q in Q, Z in
in Q and

f u
{e} does 6(q, a, Z) contain mor€ than
and a in E one element'
(q,, r,
I\
BBGGBBR) (q,, t, GGBBR)
I
Accepl

any of the above two conditions is not satisfied by a PDA' it

is called as Non-deterministic
tl
PDA.
I I
ReJecl Reject
Example,
palindrome'
Construct a PDA for language L = {wwR I we {0,1}*} or even lenglh 7. Construct PDA for L = {anbc"/m, n > = 1}. Show lD for the string 'aabcc'.
been reached and make
i tns *"nptr, ttt" pDa ia/decide that the middle of the i/p string has
and tries to match the
(Apfl 2014)
tfrr'r.*na .nJi.", pOA goes io the state; rvherc we POP the symbols
Solution
'-
remaining i/p symbols with the contents ofthe stack' L=(a"bc"/m,n>l)
iipoi gr.it* tieht, and ifthe input is ofthe tom wwR, then inpus will malch' M will emptv 6 (q6, a, R) = (qq, BR)
its stack anithus accept the input string. We push 'B' for '0'
and 'G' for l '
 't'

I r Pushdown Automata
a T.Y. P ll-Theoretical Computer Science I E . Pushdown Automata o"
ullt0t
T.Y. P tl-Theoretical Computer Science
The tmnsitions (iii) and (vi) show the nondeterministic natue ofPDA.
6 (qo, a, B) = (qo, BB)
This is a typical example of NPDA which cannot be converted to'equivalent DPDA as NPDA is
D (qn, b, R) = enor
super class ofDPDA. Hence the proof.
6 (q5 c, R) = enor
6 (qo, b, B) = (qr, B)
6 (q1, b, B) = enor 8. W tg a short note on PDA moves.
6 (qr, q B) = enor Solution
6 (q1, c, B) = (qr, e) The PDA moves will be of two types:
6 (qr, c, B) - (qr, e) i. In this an input symbol is used. Depending on the inpul symbol, the top symbol on the stack
6 (qz, e, B) = eror and tlie state ofthe finite conhol, a number of choices are possible. Each choice consists ofa
6 (qr, €, R) = accePt next state for the finite control and a (possibly empty) string ofsymbols to replace the top of
6 (qz, b, B) = enor stack symbol.
6 (q2, b, R) = enor After selecting a choice, the input head is advanced one symbol.
6 (qz, a, R) = enor
6(q, a, z) = {(Pr, tr), (P,, 1. ... (P,,IJ}
6 (q2, a, B) = enor
ID for'aabcc' where, q, Pi: (l < i < m) are states
(qo, aabcc, R) F (qo, abcc, BR) a e X, Z is stack symbol
F (qo bcc, BBR)
Ii ef*(1 <i<m)
F (qr, cc, BBR)
is a PDA in state q, lyith i/p symbol a, top ofstack symbol Z.
F (qr' c, BR)
F (qr'e' R) For any i, PDA entffs in state Pi, replac€s symbol Z by string y1 and advances the input head
= accept one symbol.

Accessible ID's for the aboYe PDA

when i/p h 001100 It is not possible to choose state Pi and string'y; for somc i *j in one move.
ii. This is called e - move, is similar to first €xcept that the input symbol is not used, and the
(q1,01100, R) ---, (qr, 01100, €) --.> Rejec't input head is not advanced afler lhe move.
This type ofmove allows the PDA to manipulate the stack without reading input symbols.
I
(q1,01100, BR) 6(q, e, Z1 = {(p,, t,), (p,, tJ , F- tJ}
l\
v\ (qr, 1100, R) (q,, 't1m, s) Reject
is a PDA in state q, independent ofthe input symbol being scanned and with Z the top symbol
(q,, 1100, BBR) -.> -) on the stack. can enter state pi and replace Z by y; for any i, 1 < i < m.

I Here the input head is not advanced.

(q,, 100, GBBR) Exornpie, consider a move in which PDA writes a s),rnbol on the top of the stack, 6
t\
+\ has a value (q, y)
(qj,00, GGBBR) (qr, 00, BBR) where, lll
=2
I I i.e. 6(q,,0, R) = {(q,, BR)} lyl = z.
(q,,0, BGGBBR) (qz , o, BR) ---) (q,, €, R) --t (qr, 3, e) I
t\ Accept
I If 11l > 1, it allows to increase the length of stack
If lyl = 1, the PDA would simply replace the top symbol by a new symbol and
by l1l new symbols.

(qr, r, BBGGBBR) (qr' {:, GGBBR)

would not increase the Iength of stack.
I I This allows us to let y = e, when we wish to POP the stack.
Rejecl Relect
 tk
T,Y. P ll.Theoretical Computer Sclence t @ i Pushdown Automata ut$0i

9. DPDA is special case of NPDA. DPDA and NPDA are not equivalent' Justify
Solution
For finite Automata, the deteministic and nondeterministic models were equivalent with respect
- to the languages acc€pted.

The same is not tru€ for PDA. There is some class of languages which are not acc€pted by any Answer the followin ark Ouestions) i
DPDA but are accepted by NPDA. As shown below.
.
The languages acc€pted by deterministic pushdown automata include all regular languages and
are a prop€r subset of the context free languages. This family of languages, which is important for l. Diffsrentiato between FA and TM. (Apfl 2012)
programming language definition and parsing consists of the languages that can be generated by Solution
LR(k) gammars. i14
i. Tape head: unidirectional Tape head: bidirectional
i.e., DPDA's accept a class of languages that is between regular languages and the CFLs.
I Only read head present. Read and write head present
The languages accepted by NPDA, include all the languages which are accepted by DPDA and ii lnput tape is filled with special blank symbol 'B'
lnput iap€ not necessarily filled wilh
which are not accepted by DPDA. i.e. all the context fiee languages. e symbol.

lnput tape lixed at one end and lnput tape is infnite at both ends
accepted by infinite at other

accepted by Transition sonsists of (Q, , )+ Q. Transilion consists of (0,0 + (0, r, { L, R, -} ).

Languages
accepted by
2. Write tuple for LBA. (October 2012)
NFA or DFA Solution
LBA is defined formally by;
M = (Q, L r,6, qo, B, l. $, F)

where, Q is the finite nonempty set ofstates

I q f is the finite set ofinput alphabets

o, f is the finit€ set of input alphabets
utsr0[
qo € Q is the start state

B e F is the special Blank symbol.

F e Q is the set offinite sets.

I eI left end marker which is entered in the leftmost cell of tlrc input tape and prevenb th€ Read /
Write head from getting offthe left end of the tape.

$e Iis called rightend marker which is entered in the dghtmost cell of the input taPe and
preyents the Read / Write head from getting offthe right end ofthe tape.

(').
T,Y, P ll-Theoretical Computer Science t r Turing irachine 0llt0i
 ()"
T,Y. P ll. Theoretical Computer Science a FA r Tuing Machine o"
eliei
T.Y, P ll. Theoretical Computer Science r E r Turing lMachine
urEt0tt

3. Construct TM for L = (a" bz".t l n > l). (October 201 2) 7. Define recursively enumerable languags, (October 2013)
Solution
Solution
L = (abbb, aabbbbb A language L over the alphabet I .rur.,ubl. ifth.r. i, a turing machine T
is called recursively

qo
E
(qo,x,R)
l'lj.,X.,..
(q1,Y, R)
that accepts every word in
complement,ofL (every word in
L and either rejects

f* not in
or loops
L)
for cvery word in the language L', the

q1 (oo,a,R; (oz,v,n; Accept (T) = L

ql (os,v,L1 Reject (T) + loop (T) = L'
q3 (qr,a,L) (qo,x,R)
Exanple: Thelngoage L = {a"b" a") is accepted by TM and loops or rejects all words not in L.
qd (q5,Y,R)

q5 err0r (0.,e,-; 8. Giva diagrammatic representation ofTuring Machino (TM). (October 201i)
q6 Accept state Solution
01234567----'
4. State true or falsa: Every recursive language is rocursively enumerable. T;fbTbT;TB]-B l-B
(Apfl 2013). Read/write
Special blank
head lnput
Solution lape
symbol
Finile control Qo

True as in Recunive language L a TM T accepts every word in L and rejects every word in L' and
in Recunively enumerable language a TM T accepts every word in L and either rejects or loops for 9 Construct TM whlch recognize well formedness of parenthesis ove((,[(,],1,)].
every word in language L'.
(October 2013)

5. Give diagrammatic ropresontation of TM. (Apfl 2013, October 2013) Solution

,
Solution
Lf it ..i I I lr !. a r.:: .'. i I . lxl.
qo {qo, (,R) (qo, L R) (qo,(, R) (qi,x, L) (a,, X, L) (q3 X, L) {qo, x, R) (q4, B)
1 ql (qo, x, R) (qo, x, L)
fB-l B 0? (qo. X. R) (a,. X. L)
Read/write q3 (qo,X, R) (q3, x, L)
head Special blank qi Accepl slate
lnput tape symbol

10. Dofino lD of Turing machine. (Apfl 2014)

Finite control Solution
AnlDofaTMisastringo,pywherep-curentstateofM.Thei/psbingisdividedasoyas
6. Construct TM for L = (anb,c"/n, m t l), (Aprit 2013)
i. l't symbol in y is cunent symbol 'a' under Read/write head and t has all remaining symbols of
Solution the input string.
Language set L = {abc, aabcc, abbc, aaabccc, aaabbccc, .......) ii. The substring d, ofthe input string formed by all the symbols to the left ofa.
IITE
9o (0,,x,n1
x 11. Design TM to check equal number of 1's and 0'" oysl ! = {0, 1}. (Apil 2014)
Solution
9t (q, a,R) (q, b,R) (oz,x,L1
(q3,b L) (q:,x,1)
I IY
qo (0,, x, n; (q3, Y R) (qo, x, R) (qo, Y, R) (qr, B, -)
ar (q1,x,R) (o:,u,1; (oo,x,r; (q4,B,R)
q1 (q, o, R) (qr, Y, R) (q1, Y, R)
qa (q4,b,R) error (q4,x,R) accept (qo, x, R)
q2 (qr, o, L) (qr, Y, L)
q3 (q., x, L) (0, t, n; (q3, x, R)
qa (q., l, L) (q., x, L) (qo, Y, R)
q5 Accept State
 r Turing Machine
o. T.Y. P ll- Theoretical Computer Science i r Turing Machine
a
ul$0tt
T.Y. P ll- Theoretical Compuier Science
ulSl0ll
'
The same approach is used in composite TM i.e., to solve a given problem using a TM, we can
'12. Stato truo/fatse: Multitrack TM has multiple
tapes'
combine two oi more turing machin€s such that output of one TM acts as one of the input to the
Solution second. Each of these Tlvls solve a part of a given problem. sucli a machine is called composite
False Turing Mrchine.

i3. LBA is non-doterministic TM: state trus / false Construclion of Composite TM

Solution We can cons&uct a c.omposite TM by executing first one TM and then another' If T1 and Tz are

, True TMs, with disjoint sets of non-halting states and transition functions 6r and & respectively, we
,l4. write Tr Tz to denote lhis composite TM
Writo lD of LBA.
Solution i. The set ofstates is the union ofthe two sets.

In LBA, the ID is denoted by (q, w, k) where q e Q'

we f and k is some integer between I
ii. Tr Tz begins in tlre initial state ofTr and executes the move ofTl (using 61) up to the point
and n. wheri Ti woutl halt for any move that would cause Tr to halt in the acrcpting state, T1 T2
The transition ofthe IDs is similar except that
k changes to k - I if the Read/Write head moves to executes the same moYe except that it moves instead to the initial state ofT2'
the left and to k I{ifthe head moves to the right'
iii. At this point tlre tape head is positioned at the square on which T1 halted. From now, the
,l5. State truerfalse: emumerator TM is a TM with
an output printer' moves ofTl T2 are the moves ofT2 (using &2).

Solution iv. Ifeithsr Tr or T2 would reject during this process, Tr Tz does also
True
input tape 6f UTM?
v. TrT2 accepts Fecisely ifand'vhen T2 accepts.
{ 6. What information should be given/ rocorded on the
Solution
vi. In order to use this composite TM in a larger context, in a manner similar to a transition
diagran, but without showing states explicitly: we Mite: Tr + T2
i. The description ofT in terms of its operation or program area ofthe tape'

ii. The initial configuration ofT iestarting state and the symbolscanned (stat€ areaofthe
tape)' vii. We can also make the composition conditional,. depending on the cunent tape symbol'
T
when

T1 halts. We write: T1 a T2, which stands for the composite nachine Tr T Tz where is:
iii. The data to be given to T (data area ofthe tape)'

Answer the follow i!s (5 Ma4!s q!99ti9!s)

(a, a, S)
tr
hlalks lor fhese Quesrb ns maY varY fron 4 to 5.

(Apfl 2012) Fron lhis we can sqy lhot:

1. Explain iterative and comPosite turing machines'
Solution A TM is not always assum€d to stafi with the tape head on the left4ost square of the tape When
u fU iullt to .u..y our some specific task is used as a component of a
larger TM, it is likely to be
we saw how two or more tunng
Iterative turing machine: [n composite turing machine' called in the middL ofthe computation, when the taPe head is at the spot on the tape
where the task
problems'
machines can be combined together to solve complex needs to be performed.
machine ln an iterated turing It may be thal the TM's only purpose is 1o change in some other specific^way the tape contents
An iterated tudng machine is a special case of composite luring the comPonent that
,".r,*"it. output Jfthe TM itsellii given as an input to itselfrepetitively' and/or head position so as to ireate a beginning configuration appropriate for
follows.
Exomple, nppose M is a TM which computes a square
of a number' Then.such a machine can
by each iime taking the input.as the next inpul lhus'
Definilion of composite TM
alsu be asked to compute square ol u nu*bt'. it
u'ing-tomposition and iteralion to.solve a Yery complicated It €xecutes the TM T1 (rgecting if Tr rejects and looping if T1 loops) if and when Tr accepts'
;;; ;;";;1il-.-ffi..rri il,I uv executes T2 ifthe current tape symbol is 'a' and rejects otherwise
pr"ur.r. iiir."ri.pt has consideiably influenied the existing programming paradigms.

composite TMr ln a top-do\4n structured progamming

technique. a complex progamming 2. Construct a Turing machins with input alphab€t (a, b, c) that accepts strings in
..nhlem is hroken down into smaller sub problems' ihese su6 problems are
then into fu herdivided which tho firsl c i; precedod by the subsliing aaa. (April2012)

ffi:J';;;ffi;; ;; ;;. i; ;;"'v

ihe enrire problem is solved bv solving these sub
on'
problems

ura ,trg,t a -t*.t, o[one problem on lhe inputs to the second and so
 ( T.Y, P ll- Theoretical CompuGr Science a F7 a Turing Machine
a
T.Y. P ll- Theoretical computer Science I Ic;] I Turing Machine t
utSt0tt

If6(q, x) = (P, y, R) then the change in ID is:

Solution
bl c ls Xt X2.,. xi-l q Xr... xi F xl x2 .... X,,I y P X,+ I xn.

qo (qo a, R) (qo, b, R) (q,, c, L) (qs, B, R)

Thus Ii t- Ir. defines the relation among IDs.
Qr (qz, a,L) ( qz, a' L) (q:, a, L) Error

Qr (qu a,L) ( qr, a, L) (qr, a, L) Error ll denotes reflcrive - transitive closure ofrelation F
Ol (q.' a,L) ( qr, a, L) (qr, a, L) Error

(qo, b, L) (a4, c, L) (q5, B, R)

q,1 (qo, a,R)
Ifll PI, then we split it as: Ir F t: l-... F In for some IDs 12, ...1^- r

9s Accept State

3,
-' What is solvable and unsotvable problom of TM? Give any one example
of 5. Explain in brief variations of TM.
ilnsohafte proutem' $Pfl 2ua) Solution
Solution a. Multitrack Turiry machine: A Multitrack Turing machine is a specific type of Multi-tape
problem in the class'
i.
-' Solvablei If there is a TM (or algorithm), which when applied to any TM which has only one unified tape head. In a standard n-tape Turing machine, n heads move
always,eventually terminates with the conect yes / no answer, then we call the problem
independently along n tracks. In a n-track Turing machine, one head reads and writc's on all
solvable. facks simultaneously. A tape position in a n-track Turing Machine c.ontains n symbols ftom
problem in the class'
ii, Unsolvable: Ifthere is no TM (or an algorithm; which when applied to a the tape alphabet. It is equiYalent to the standard Turing machine and therefore accepts
eyentually terminates with the conect answer yes. we call the pioblem unsolvable' precisely the recursively enumerable languages
Exanples of lLnsolvable Ptoblens:
Control
l. For any programming language, to determine whether or not' One lape head to read
k symbols f.om the k tracks
a. A given program can loop forever on some input' al one step.

b. A given program ever produces an output'

Track 1 I [TT_I
]II
I

f'ack2
c. A given program eventually halts on the given input' : tr
whether or Track k ITJ rrT_l
2. Consider a program to evaluate xn + yn = z', n > 2, the problem to determine
not the Ptogmm will halt ifand when a solution is found'
b. Two-way TM: The tape is infinite to left and riSht end. So the input tape lool6 like -
4, Write a short note on TM moves.
Solution B a\ a- al a" B B B

The 6 (q, x) changes the ID of TM. Such a change in ID is called a move'

If 6 (q, x) = (P, Y, L).
Let i/p string is x1, x2 . . xn. t-
I l-tnrle state
Cunent symbol under Read I Write head - x;
I automata
.. ID before processing symbol xi is x1x2 . . . xi' I q x! xi+ l xo'

After x; is processed ID becomes Here lhe input string is ar. a2. ar.... a.. The tape is loaded with adtlank symbols(B) to the left
xt,x:...x,.2Px, )Yr'.'.. x,' ofa, and to the righi of a.. So if qp is the initial state ofthe TM, ID coresponding to the initial
state will be qe, a1,a2,.....an B.
This is representerl asi x1,X1 ...xi-lqxi ."xnl-xl "x,-2Px, ryx,tr" xn'
 r Ik i (h
T.Y, P ll- Theoreticat Computer Science
t Turing Machine T.Y. P ll- Theoretlcal Computer Science a Turing Machine
ul|0t
heads are increased. The assumption wite only once tape
c Muhitape TM; Here the number of tapes and read/write
of a finite control with k number ofheads'
is all the tapes are rwo wa1 infinite lt consists a b

Finile conirol
head 1 FSC

..Tape1
R/W head 2
.-.Tape 2
I-T-ftT_ttT_r
R/W head 3
. . Tape (
The language enumerated by an enumerator E is the collection of strings that il eventually prints
out. E may generate the strings in any order, possibly with repetitions. We must also note that there
each of
of the finite control and the symbols scanned by is no input to an enumerator. Also, ifthe enumerating TM do€s not halt, it may print an infinile list
ln a single move, depending on the state
the tape heads, the machine can - ofstrings. A formal definition ofan enumerator follows

a. change the state Delinition

by its tape heads An enumerator E is a 6-tuple r herc
b. print-a new symbol on each ofthe cells scanned

c. move each of its tape heads, indePendently, one cell to the

left ff right or keep it stationary' l. Q is the finite set ofstates;
plays important role in FAs and PDAS lt is
2. Iis the print tape alphab€t, not containing th€ blank symbol B;
d. Nondeterministic TM: Non-det€rminism.
convenient but not cssential in case ofFA' 3. f is the work tape alphabet, where{B) gf and Igf;
DPDA'
Pal is a CFL which can't be accapted by any 4. 6: Q x f-+ Q x f, x {L, R} is the transition function for the nro tape device
power that nondeterminism fails to add any more'
Turing machines have enough computing
5. g Q is initial state
qo

Anon--tleterministicTMdiffersfromdeterministicTM,wehaveseenearlierinthissection'
state q and tape symbol X' 6 (q' x) is a set
oftriples' 6. qr,,,r e Q is final state
,ii"'n **;0, such that foreach
Exomple:
"riy
{(qr, Yr, DI), (qz, Yr, D, (q* Y' Dk)}
,11 = 1 a"b" nZ 0 ) the enumerator will output the following things -
where, k is finite integer'
{ e, ab, a2b2, arbr,......)
to be the next move
A NTM chooses at each step, any of the niples
symbol ftom another and the direction from
But it cannot pick a state form one triple, a tape
yet another triPle.
7. Explain operations of UTM.
dehned by a function from 6 : Q x
--r f Solution
From this we can say that transitions in NTM are
subseis ofQ x f x {L,R}. Examine the input to make sure that th€ code for M is legitimate code for some TM. Ifnot U
halts without accepting. Since invalid codes are assumed to represent the TM with no moves,
o Explain Enumerating TM and such a TM accepts no inputs, this action is correct.
Solution ll Initialize the second tape to contain the input w, in its encoded form. i.e. for each 0 ofw, place
Turing machine can use the l0 on the second tape, and for each I ofw, place 100 there.
An Enumerator is a Turing machine with an outPut Print€r'-The
sives a schematic of
an
p'#:;;;';;;; a.ri.. io p,int rh' iollowing
sri;;; diagram (Blanks on the simulated tape of M, which are represented by 1000, will not actually appear
enumerator on that tape, all cells beyond those used for w will hold the blank ofU. However, U knows
that, should it look for a simulated symbol ofM and find its blank, it must replace that blank
by the sequence 1000 to simulate the blank of M)
Place 0, the start state ofM, on the third tape and move the head of U's second tape to the first
simulated cell.
 (k
T.Y. P ll- Theqretical Compuier Science t a Turing Machine ut0n

To simulate a move of M, U searches on its ffist tape for a hansition 0it0l0kld10'such

that

0i is the state on tape 3, and 0 is the tape symbol ofM thal begins at the
position on tape 2

scanned by U.
This transition is the one M would next make. U should:
a. Change the contents oftaPe 3 to 0t i.e. simulate the state change ofM, !o do so, U first
changles all the 0's on tape 3 to blanls and then copies diftom tape 1 to taPe
3'

b. Replace d on the tape 2 by 0r i e. change tho taPe symbol at M'

If more or less space is needed (i.e. i I l), use the scrdtch tap€ and the shifting over
technique to manage fte sPacing.
c. Move the head on tape 2 to the position ofthe next I to the left or righ! respectively,
the move
depending on whether m = 1 (move left) or m = 2 (move right) Ihus, U siritulates
oiM to the left or to the right. Thus U simulates the move ofM to the teft or io the righl
has no tansition that matches the simulated state and tape symbol' then
in (iv), no
If M
transition rvill be found. Thus M halts in the simulated conliguration and u must
do likewise.

lf M enters its'accepting state, then U accepts.

o Section-l!
Question Paper Solution (Yearwise)
utst0ll
 October 2015
Theoretical Computer Science

l. Attempt all of the followlng: [10x1=l0l

If;l nullstring.
Doflns (ch 1)
Solution
Null String: A string having No symbol or zero symbols is called Null string and is denoted by (e).
IIb
Writs smallg3t posliblo sting from the ,ollowlng rogular expro$ion (ch 1)
(a + b) (aa)' (ab)
Solution
aab

Deline ambiguour gnmmar. (Ch 4)

Solutioo
Ambiguous grsmmsr: A CFG is called ambiguous iffor at least one word in the language thal it
posible derivations ofthe word that conespond to differ€nt syntax tees.
gen€rales there are two

DFA has an E.transaction. Stato truo or falso. (ch 2)

Solutiou
False. DPA does not have r tmnsaction.
1E
Describe ths language forthe folloyving regular sxprsssion:(00 + ll) (0 + if (00 +11) (Ch 3)
Solution
The language L which starts and ends with 00 or 1 1 and may contain any number of 0's or 1's in
hetween.

Doins nullabl€ symbol and u3etgs3 rymbol. (Ch 4)

Solutiotr
Nullable symbol: In a given CFG, a non-terminal N is nullable if:
a. Thae is a production N or,
b. There is a derivation that starts at N and leads to e.
*
i.e. N+e
G
Useless symbol: Let G be a context free grammar. A symbol xe (V v f) is usell if there is a
derivation.

S+uxv.+w,
GG
where, x e (VvE), u,v e (VuE)*, andw e Et. A symbol that is not useful is said to be
weless symbol.

o"
T.Y. P-llTheoretical Compurer Sciencer
! . 2015 October 1693 urst0i
 o, r 2015 October
o.
T.Y. P-ll Theoretical Computer Sci ence't
r 2015 october T.Y, Pll Theoretical Computer Sciencet ut8t0!

where, k is flnite inleger.

E- (cn4)
A NTM chooses at each step, any ofthe triples to be the next movp.
0efine TYPe'2 grammar'
Solution But it carmot pick a state form one triple, a tape symbol from another and the direction ftom yet
side of each Production rule' that is the
Tvne 2 smmmars have more restriction on the left-hand anotha triple.
ie a-+pisof theform A-+p
lni'il "
tiigi" i"*,erminal symbol
From this we can say that ransitions in NTM are defined by a function tom
and non terminals
where, A e V, p is string ofterminals l-+subselsofQ lx
6:Qx x {L, R}.
(ch 6)
between TM and FA. 2. Attempt any two of the following: [2x5={01
solution Eal
E6iinstruct oFA to accept substring 'lol' or '001'. (Ch 2)
FAs are use lo accept oI recognize Solution
FAs are use to accept or recognize only
recursively enumerable languages'
regular languages Regular expression is (0+l)t 101 + (0 +l){ 001. Both the minimum strings end in 01 but sta
so it TM's have auxiliary memory so it can with 1 or 0. qohas two input symbols 0 and I to reach qt. The remaining DFA will be same as ending
FA conlains only p mitive memory
remember Previous Symbols in 01.
cannot store inpul read
0
Tape head is bidireclional. TaPe is 1 0 1

Tape heaq is one directional' Tape is

c osed
o qr q1
infinite al both he ends.
at one end 1,0 0 1
q, q1
q1
Tape is Read^ rite tape
Tape is read onlY q? q? o

q3 q2 q1
1 (ch 5)
Defne lD of PoA. 1

SolutioD
at any tim€ and the remaining i& string to be
ln FA, ID is defined as cunent state of FsM Construct Moore machino and melay mach ins which oulpuB even or odd according to
processed to describe the finite state
machin (ch 2)
numbor of b's sncountgred are even or 0O6 or"1 2 =(a, b).
we need to specif, the curent state, remaining
i/p string to be
In PDA. as we have stack, solultotr
pro..rr.a ,n. ty,bols on the pushdown stack Moor€ Machine
-a (q' x' o) where q e Q' x e I' and oe f*' b a 5
. lfM = (Q, ,, f, 6, qs, za, F) is a PDA, then an tD is (Output)
. a b il,
a
q,
i.e., q is cunent state' qo qo even

w is inPut left H41ead . b

q1 o qo odd

n is on stack (first symhol ofa is top ofstack) Melay Machine

(q' aw' Zo) f- (p' w' po)
IfM = (Q, ,, l, 0, q0, Z0, F) is a PDA, we say b/even a/odd 3 )t
a b a b

lf6(q, a, Z) contains (p, p) a may be e or an i/p

symbol a/odd
*. q, qo odd even

(qr' BG) then l'

i.e.. lfwe have a transition 6(q1, 0, G) -+ b/even
q, ql qo odd even

(q, 011, GGR) F- (q1, 11, BGGR)'

Construct FA tor tho follorf,ing regular expression (ch s)

a(a+bltb+b(bia)'a
Solution Solution
TM' only in the function 6' such that for each r = a(a+b)+b + b(b+a) *a
A non-deterministic TM differs ftom deterministic
(q, x) is a set oftriples'
state q and tape symbol X, 6 Il l1

{(qr, Yr, Dr), (q:, Y:,

D, " " (q' Y' D*)} =a(a+b)tb
+ r1
 o" . o.
T.Y. P-ll Theoretlcal Com
s"i"n""r !. 20'15 October 0n T,Y. P-ll Theoretical Compuler Sclencea 2015 October utst0i

r:=b(b+a)*a 3. Attempt any two of the following: [2x5=101

3 a
,,=" @j@,,=b @-3@ Construct TM for language: L =
Solution
(a' bnc' I m, n > = 0) (ch 6)

rr=(a+b)t 16=o+a)* Language set L = {e, abc, aabcc, abbc, aaabccc, aaabbccc, .......}

= (11 + r), = (r4 + rr'l :. .4 b c x l.rB.

qo (q,, x, R) Accepl
ql (0,, a, n; (qr, b, R) (q/ x, L)

e €
e e
q2

q3 (q1, x, R)
(q3, b, L)

(q3, b, L)
(q3,

(q3,
x,
x,
L)

L)
I(q.,, B, R)

lj. qr (co, b, R) Error (q., x, R) Accept

l1
€

€
Construct NPDA for a language: (ch 5)
L= {ooRloe ( 0 + 1)'}
€
SolutioD

15:=q q, rhe PDA M is ({ql q2), {0, 1}, {R, B, G}, 6, q, & 0)
q7
where 0 is
l 6(qr 0, R) (ql, BR)
i 5(q,, 1, R) (qi, GR)
iii. 6(q,, o B) {(qr, BB), (qr, s)}
V 6(q,,0 G) (q,, BG)
rt:=hlt14
6(q1, 1, B) (q, cB)

9z
vi 6(q,,1, G) {(q1, GG), (qr, e)}
ar 9a r5 9r
vii 6(qr, o, B) (qz,
")
6(qr, 1, G) (oz, e1

6(qr, e, R) (Qz, e;
tz:=f4f6I3 6(qz e R) (Q:, e;
€

Define Greibach Normal form (GNF). convert the following grammar into GNF.
S -+ ABAIABIBAIAAIAIB (ch 4)
I=fl+12 A+aAla
B+bBlb
Soluaior
GNF fA context free grammar G = (V, I, P, S) is in GNF if each production has one of the
following lorms:
A -+ a Ar Az Ar ....... An
A-la or
S-+e
where, aeLA,eV-{S} for i= 1,2......n
 ah . 2015 October
o"
T,Y, P"ll Theoretlcal Computer Sclencea ut8t0t
Sclencei 2015 October
T.Y. PllTheoretlca I ComPutet
4. Attempt either A or B: [2x5=101
lonversion of CFG into
GNF
4EE
S+ ABA IAB IBA IAA IA IB Show that the rsgular sets ars closed undst complsmentation' (ch 3) t4l
Soludon
A+aAla
Let L be L(M). Some ofstates ofthis FA, M are final states and some are not.
B)bBlb B eliminating unit productions
*o *i productions s +A s -) Let's revene the states of each state, i.e., if it was a final slah mite it non-final and if it was
- if,o" ur" 'nd non-frnal, make it final.
I albB lb
-rABA IAB I BAI AAI
aA
S
The new FA acrcpls all sring that were not accepted by the original FA(L).
.'. the grammar is
albB lb .'. Machine accepts the language L'.
s+ase I AB I sel AAlaAl
A+aAla .'. L' is a regulm set.

B-)bBlb By using F.A. we can prove this,

The production Constuct DFA for a language over {a, b} which contains all strings not having "bba" as a

S + ABA I is not in CNF substing.

a b
. . converting it in CNF a,b
b b a
S+AB1
BI+BA butS-)BA .'.Br+S
.. S)AS Make complemenr of each state.

. . Grammar ts i.e. make all final states, non-fllral and all non-fmal states fmal

s rAS IAB I BA I AA I aAlbB I

alb a b
a,b
b b a
A-raAla
B-+bBIb
This FA represent the language which contains "bba" as substring i.e. complement of original
Replacing S bY A1
FA(L).
AbY42
BbYAI
., We can prove that complernent ofregular set is also regular

Ar -r AzAr I AzAr I ArAz I AzAz I

aAz lbArl a I b 4EE (ch 2)
Mlnimlze lho following DFA: t4l
A2-+aA:la Transition table
Replacing & in Ar \r
left recursion a b
ili,oiiiL,"^ < all A2 and 43 so there is no immediate
o,
we get final.cNF
Ci\
bv Ar productions q, q2 q3
e, ti"ouciions and Ar Start
"'"1]i"il,il, bAr I a I b
''"il -*",'i*, f aArrbArAr tbAt aAzAz I aAI I
aA2A1' q1 q. q3
q3 q. q3
A2-raA2la
9r 9r
Ar -+ bAr lb
Replacing 41 bY S, Az bY
A and Ar bY B' 9s 9z Qs

r 1*fr *u,
t bBA I
t
*
bA I aAA I aA I aA I bB la I b where M = ({q1............q5},(a, b},6, ql,(q5})
"t
n-+aAla
B-+bBlb
is the final GNF
 o" o,
T.Y. Pll Theoretical Computer Sciencea t, . 2015 October

T.Y, P-llTheoretical Com

s"i"n"e. f r 2015 October

6(qo, e, B) -r ERRoR -+ if No 'b' afler a

iolution
a b
q2 q3 6(qo, b, B) (q1, B)
ar
q2 q3 q3 q2

q3 6(9r, b, B) (oz, e1 Read 1e b, No change in stack. Read 2d b, PoP

q3 qa 9r
q.r q3 qs qa )
6(qr, b' B) (q1,8)
*qs q2 q5 qs
qr q2 ft q'r
6(q1,6, B) ERROR -+ Afler readjng 1'r b, string ends.
Mark 'x' : One final x one non final state
qr, q:' 6(qr' qs) = . (q,,q)=* + After reading 1't b, 'a' appears.
(qr qr)
- 6(qr, b) = 6(q, b) = ' 6(qr, a, B) ERROR

Similarly, ma* (qz, qn), (qr q.) as * ($, --, Empty stac[ accept
6(qr, e, R) El
mark (q" qr), (q2, q3) as x

mark (qr, qr) as x 6(qr, e, R) ERROR -+ Afler reading l't b, string ends.

This shows n0 two states are equivalent'

So DFA cannot be minimized' 6(qz, e, B) ERROR ) No. of a's # (no of b's) '2
ERROR No. of b's don't malch
c (ch 4) t21
6(qr, b, R)
'
Explain tYPes of regular grammar,
Soluaion
4 EIE (ch 4)
Construct CFG tor the following: t4l
There are lwo
"'- forms of Productions
appear as rightmost symbol in
each Prcduction' ;. 1'13'b'cnln>t,m>0) I

o n-ign'-lirr* gr,,rtar;A non-terminal symbol ii. L=Lr^L,

Exanple:G = (V',, P, S) wnere L, = la" o a" ; n > 'l), L, = 311 naving odd lsnglh over {a, b}
v= {A, B}, r= {a) Solution "1r;nn"

P = tAJaB B-+altl i. The language set is

symbol in each Production' L = (ac, abc, aakc, aabbcc, aabbbcc,.......)
b. Lefr-lineor grannar: Anon-terminal symbol apPesrs as leftmost
t' P, s) Terminal string is ac => S+ ac
Exanple: G= (v,
To genaate multiple a'ci :>
v= {A, B}, E={a}
S -r aSc
P = {A-rBa B-+ala}
To generate multiple b's, we need another non'teminal to be introduced derived
B a
a language: L= (a" b'zn I n > ll Ph 5) t4l
Construct a PDA which accopts from S.
Solution S+aAc
B} 6' qo R 0)
iet the PDA M = ({qo, q,, qa qr) {q b) {& A-+bAlb
6(qo, €, R) + ERROR ii. Looking at the two languages, it is clear that:
can't start with b or e
Language Lr will have all strings over {a, b} having odd length
6(qo, b, R) + ERROR )
and language L2 itself is containing strings of odd len$h

8(qo, a, R) l (qo, BR) ..L=LrnLr=Lr

Push B for all a s

6(qo, a, B) + (qo, BB) )

 o. April2016
T.Y. P-ll Theoretical Com pu!er Sciencet . 20'15 October U*INtr

It cannot be L2 becaus€, L2 may contain saings aa4 bbb

or aab " ' which are not Part ofll Theoretical Computer Science
To g€nerate Lr language set:
Lr= \abo"aaba4 aaabaa4 ...-....\ 1. Attempt all ot the following: [l0x{=10]
S + aba to generate terminal sting' Eal (ch
bottr sides of'b'' What aro tho prop6, prafixe3 and ptopsr sufrixe3 o, th€ string "lndia"? 1)
S -) asa to generate multiple a's recursively, on
Solulion
Combining it together Proper prelix: (e, I, In, Ind, Indi)
L=Lr.rLz S=aSalaba P suIIL: {e, g i4 dia, ndia}
lEl
B c
Stats th€ differences between recuBivo and
rscur3ivo enumerable languago' (6h 6) 121 Dsflno loft linoar and right llnear grammar. (ch 4)
Solutioo
Solution leftnost symbol in each hoduction.
Lrft-Linear Grammsr: A non-terminal symbol appbars as
ln recursively en! mera ble larE uage a Ttu T
n tec!l rsive language L a TM T accepts Exanple,
rd in accepts every n L a nd either rejecls or
every word ln L a nd rejects every c=(v,E,P,s)
lot word tn L
L
It can be deiend as
It can be defned as v={A,B},r={a}
Accept (r) = L
Acced O = L p={ArBa
Reject (T) , L'
Rejecr(r)+loop(I)=f B-+ale)
Right Linear Grlmmrr: A non'terminal symbol appear as rightmost symbol in each
tecursve language rs also The converse is not true.
E very Production.
recursively enumerable because the Ttll for
Example,
the recu rsVe la ng uage can be used lo
sali both defin ions.
'lhe la nguage L
G=(V,E,P,S)
Example, is
Ex anple, The lan s uage of all words
accepted by TM a nd lo ops or rej ects all v={A,B},r={a}
(a b th at start with a and c rashes on all
words th at do not Reject)
words not in L. P={AraB
B-+ale)

Write tho regllar oxprssslon for the follorYing FA: (ch 3)

0 1

0 1

o" Slart

utst0ll Solution
expression is: 0*01*

Compare 'I' function of Molay and iloore machino. (ch 2)

Solution
Moore mrchine: l, - is a output maPping from Q -+ A giving the output associated with each

state.
Melry Machine: l,- is a output function mapping from Q x X -+ A

o.
T.Y. P.ll TheorGtlcal computer Sclonce o
!. ,o,roon, 1693 urar0i
 o,i t .2016April
o"
T,Y. Pll Theoreti calComPuter S"i"r"" a ! r 20|6 April T,Y, PJI Theoretical Com puter Science ulSt

2. Attempt any two of the following: [2x5=l0l

(ch 2)
/Vrite down the '€-closur€' of each
state from the following FA: flal
Conslruct a 0FA to accept all decimal numbers divisible by 3. (ch 2)

Solutiotr
-rK/
,.--. " ,/A SolutioD
We oeate 3 sets Rs R1, R2 containing the numbers giving remainder 0,
& = { 0,3,6,9, 12, Is....}
Rr = {1,4,7, 10, 13, 16, . . . .}
l, 2 respectively.

. e - Closure (qo) = {qo qr}

&={2,5,8, II, 14, 17,...}
e - Closure (qr) = {qr) State q0 accepts all numbers giving 0 remainder. q1 accepts all numbers giving I remainder and
(ch 4) q2 accepls all numbers giving 2 remainder. We use only single digit numbers for the tansitions.
Stato the two different ways lo simplify the CFG'
&={0,3,6,e)
Solution Rr = {1, 4, 7}
Elimination of useless sYmbol
R, = {2, 5, 8}
Removal of unit Production 0 6,9 0,3,6,9
Elimination of e Production
(ch 1, 4,7
sensitivo grammar' 4)
ffiu ,""n,n"" used tor context tree grammar and context
Solution 2,5,8
"" Free Grammar: Push Down Automata
(PDA)
roi"ir,ir. or.o tot context
ii".iir" ,t"o irt c"ntext setrsitiYe Grammar: Linear Bounded Automata (LBA)
2.5,I I 2.5,8

(ch 5)
Diflerontiate between PDA and FA,
Solution
Diflerence between PDA and FA
0,3,6,9

FA's are used to accept or recognize

FAs ale used to a ccept or recogn ize only Construct DFA equivalent to the following NeFA: (ch 2)
context free I an ua
ar lan
it TM's have auxiliary memorY, Stack. So it
FA contains only pri mitive memory so
read can store one mbo
cannot store in 1

T is read on
fa is Read/write
1 (ch 6)
Dofine tuPles of LBA.
Sohtion
Solution
Tuoles ofLBA: G = (V,,'
1
) P. S
q,, qd
. wtiere V is set ofNonterminats
9o
q1
,i
q,
0
,l
{qo,
9t
E is set ofterminals
S is start symbol
q2 ,t q3 iq,
and P is set ofpoduction rules in the form: a +p q3 { ,l {qr, qa, qd
is at least as much as the length ofo' except
for a
il;,;J. ofp q4 ,| q5 ar
["t)* isthat-the length
o ] q.
production rule S -+ e i.e lo l< lP I

Stafi state ofNFA is qo

ofDFA = e - closure ofqe = {qo 9r, gr} = A

slart state

totitirorlr,r, 6'(4, 0) = e - closure (61A, €), 0)

set Then there is a constant n such that if z
,"tm for regular set: Let L be a regular = e - closure (6"(qe, q1, qr, 0))
is anv wordln L and lz l> n, we maywrite z= uur such that =e-closure(q2)=q2=B
l; foralli 0,uvV isinL' l)= e - closure
luv l<nantliv > 6'(4, (q5) = q5 = C
t
 o" T.Y. PJI Theoretical Computer Science r .2016April
o,
ut8t0i
T.Y. PJlTheoretlcal Com te. sctence r f 2016 Aprll
13: t5 16 rj
6'fB. 0) = €
-closue(qr=O €
o'b, ri= . - closure (q) = {9r.qr'
q} = o ar 9z I6 Q3 9o

6'(C,0)= e -closure({)={
6'(C. 1) = € -closure(0)= 0 14: f5 ft
s'iD. o) = e - closure (qz) = 9r = E q,
uip, ri = . - closure (qr, q, = (q2' q4) = F

6'(E,0) = e -closure(q;1=E
6'iE, l)= E -closue(qr)=E
6'G,0)=e-closue(0)=O
6'iF. t) = e - closure (qr, qr) = F
Final slate ofNFA = q,
(qi) = =C
.'.-fina sute ofOfA = € - closue
q5

6 ofDFA '|
0
B
D l2l l1t
B d
,c { 0 €

@
9r 9o r5
D E F f1

E E E
F o F

DFA is
f1
0

0
I=II 12
l1 9s ao l2
@
01
1
3. Attempt any two of the following: [2x5=l0l
(ch 3)
regular explsssion'
Construct FA for th€ following Detine PDA and construct PDA for: L = (an b'a" I m, n > l). (ch 5)
(010 + 00)'(10)' Solutior
solution PDA: A Pushdown automaton M is a seven tuple (Q, X, f, 6, qo, a, F)
r=(01 0 + 00)* (10)*
where, Q = finite nonempty set of stat€s
fl l7
X= an alphabet called input alphabet
., = (0r0 + 00r (10)* I'= an alphabet called the stack alphabet q0 in Q is the initial state.
rl rl & in f is a particular stack symbol called start stack symbol
Fq Q is a set offinal states
6: mapping from Q x (t u {s}) x f to finite subsets ofQ x l*.
f5
@-e@ PDA for L = {a" b'a" lm, n > 1)
Language set = {aba, aabaa, abba, . . .)
f6:
@r@
 o. T.Y. PJI Theoretical Compuler SclencE a | 2016April
0.
ur8r0[
T.Y. PllTheoretica lCompute , S"t"nc" r Er 2016 APril
B-+ArBlb
For all a's
'B' for a, for lr b' change state' for all next b's No change in slack . Final CNF is
Logic: Push .

aftu that
"-' POP the sYmbol' S-+ASIBAIAAIAB
rtre pOe M = (iqo, qr, b} B}' 6' q'p' R' $) A+ArAla
' qz) {a, {R'
6(q' iil
'. R)
---' !S9l
ERRoR I can.t sta.rt with e or b
B-+BrBlb
s(qc b, J Aq)a
BR) A2-+b
6(qo, a, R) - (q,
(qnBB)
I
Push B for all a's
6(qs, a, B) - i Conslruct CFG for the follorying: (Ch 4)
) ERROR -) ifNo a's or b's after first a's
6(qp, e, B)
(q,' B)
i. L = {ar bvcr+, I x, y > t},
6(qo, b, B) -+
(q,' B)
Read b's - No action on stack ii. A language conbining s&ing having at least ono occurrence ot'00' over (0,1).
6(q1, b, B) -) ) Solution

6(qr, e, B) -) ERROR -) if No a's at last i. S-+Ac

-+ (q, e) A -+ aAcBc I a
6(qr, a, B)
POP all a's B+bBclb
6(qr, a, B) -) (qr, e)
) ii. s J ls [0S I Sl l0s | 00A I A00
(qa t, R) -) (qr, e) -) empty stack
A-+00sls00llBl0B
-+ ERROR -+ a's before > a's after
6(qu, e' B) B+lBl0Bl0ll
6(qr, b, B) -) ERROR -) after alater, b occurs

6(qz, a, R) -) ERROR , a's before < a's after 4, Attempt either A or B: [2xsrlot
A a
3 b (ch 4) Minimlzo tho following OFA: (ch 2)
Normal Form (CNF):
Construct the following CFG into Chomsky
S -.r ABA
b
A+aAl€(sPsilon)
BJbBI€(Epsilon)
Solutiou
S -+ ABA
A-)aAl€
B-rbBle Solution
'+ eliminating e - Productions ql
A-+aAle -A+a q2

B-+bBlE rB+b q3
qa
fTtTb
qo q2
ar
Rewriting
qo q2 q3 ql q3
AraAIa S-.>ABAIBAIAAIAB ar ar
q2 qo qi
B-)bBlb tq,Tq,Tq.
S + BA IAA I AB are in CNF' lq. lq, lq,
S + ABA not in CNF conYeding mark (qo qz) (qr, qz) (qo.qo) (qr. qo) (qr, qr) (qr. qz)
S --r ABr Br JBA butS+BA Check (qs qr) 3 6(q0,a)rqr 6(qr,a)-+9r
Br-lBA 6(qs, b) j.q2 6(q1, b) --r q3
"... g _r AS (q2, q) - marked
Now A -+ aA and B + bB are not in CNF ... mark (qs, q1) x
.. converting AI = letA2 = b a, Check (q1, q)
= 6(q1, b) --r qs 6(q, b) -+ qa (q1, q) marked x
. . Replacing ... mark (q1, q) x
A+ArAla
 ( T,Y, PJlTheoretical Compuier Scierce t r 2015Apil
o,
ut3t0i
r Science a r 2016 A ril
T.Y. P-ll TheoreticalCom Pute

* 6(qo' a) +qr 6(qr, b) -r qr

l* f, T'TTI
Cheok (qo, qr)
6(q3, b) -+ qr
6(qo' b) -+ q'?
''' don't mark
6(qz, a) -+ qr 6(q6 a) -+ 9r FSC
check (qr, qr) =
6(q" b) -+ qo 6(qr, b) -+ qr
'

'" don't mark' q]

. (qo q, and (q2 = qa)
. =
. . combine [qo qr] and [qz
qr] Final state = [q" ITTTTTTI
So the Final DFA is b
s"t
The language enumerated by an ","u#[X?n,,",,to,
enumerator E is the collection of strings that it eventually
a prints out. E may generate the saings in any order, possibly with repetitions. We must also
note tbat there is no input to aD enumerator. Also, ifthe enumerating TM does not hat, it may
print an infurite list ofstsings. A formal definition ofan enumerator are as follows:
Delinition: An awnaator E is a 6tupl€ u/here
a i. Q is the frnite set of states;
A b (ch 6)
ii. ! is the print tape alphabet, not containing the blank symbol B;
Explain the typse ofTuring
Machins (TM)' iii. I is the work tapc alphabet, where{B} c F and Xcf;
Solutioo
iv. E: Qx l-rQx I x {L, R} is the tnnsition firnction for the two taPe device
Tvpes ofruring nochine , and looping if 11 loops) if and v. q Q is initial state
qo
TM Tr (rejecting if 11 rejects vi. 9p.u -c Q is final state
I' composite TMt lt "*"tll:I:.;:;*.ii"p.'tyru"r t
l2 lr
'a' and rejecs otherwise
A transition of
l,hen Tr accepls. it executes 3. Universal TM: Turing machine M is defined by its tansition function. a

consfiuction of co'np"i': Ly ..Mbv executing first one TM and then another' Il rr

and ru standard tring machine has $e form.

n'*tions 01 and 62 respectiverv' 6 (q; x) = [q, v, d]

I; ;il,:T'ilHil:1t:l.":il#il;"'"*i'n''i'i""
rhis composie TM
whereqi, q e Q, x,y e tandd e {L, R)
I" *ii. r, ir toi*ote Design oIUTM
l' "'-ti. ,o "ft'ns is the union ofthe two sets'

ii ii I, i:il;T'
point where
;; g
j'1,

Y":lo-
H: "jj,jrii ffi iT,',1"#:',:',1
T{.';"-;'.r.*itrr",
#;'lf il I#,*;
of rz'
ii,"'* i'strarl to the initial starcon
A UTM is designed to simulate the comPutations of an arbitrary turing machine M. To do so,
the inpm to the universal machine must contain a representation of the machine M and the
string w to be proc€ssed by M.
which We assune that M is a standard TM that accepts by halting. The action ofUTM, U is depicted
iii
,',
f iii'iv-:',,1'tu:11,;:;$:T*x,ii,ff",Tj1"
T, halted From no\'Y' the '
ii"',rr"t1' would reject during this process
Tl T2 does also'
by Let R(M) be the representation ofmach ine M.

R(M) W L,niversal
machino
M h6lts wilh W
Accept

"'r) U Loo!
in a manner simirar to a hansition
i. I i'r::',:':ssnH"',,tfL1[i]:ifi:::"'text'
diasram, but without sno*lng;tuto
t*ptititly: we write: T1-+Tr
tape svmbol'
M do€s nol halt

Thc ouput labeled 'loop' indicates that the comPutation ofU do€s not teminate
vii. we-can ur'o ttt" tttt t#i?i-r"i t'ilii"ia'
depending on the cunent
machine Tr T Tz If M halts and ac.4pls input w. U does $e same.
*t t""i"T' *i-Li-t*ot ior thelompo'ite
when Tt halts' il'' If M does not halt with w, neitha does U. The machine U is called universal since the
ofany TM M can be simulated by U
'l'
where is:
(a, a, s) 4E c
Explain any ono clolurg property. of regular set. (ch 3)
is a Turing machine with
an outPut Printer' The Turing Solution
t Enumerating TM: An Enumerator to nt str ings. The following dia$am
glves a Closure Proprrty of regulsr set: Regular sets are closed under union, concatenation and Kleene
as an oulpul device P
machine can use tle printer closwe, i.e., if L1 and L, are regular sets then Lr u L2, (Lt + L2), LrL2 and L* are also regular'
schematic of an enumerator
 | 20r6 April
o,
T,Y. PJI Thooretical Computer Scienca a

Proof
' Lr + L2 means th€ language ofall words in either Lr or Lz. Say regular expressions for Lr and Lr
ar€ rr and 12 resPectiYely.

Then, rr + rz is regular expression for Ll u la

' rrr2 is regular expression for L1L2
r1* is regular expression for L1i.
... All three types ofthese sets ofwords are definable by regular expression and so are themselves
.are
regulai sets.
ffi
4E a
Construct TM tor L = {ww8 lw E (0 + 'l)'} (ch 6)
Solution
Ifw=0010thenlrl=0100
.. string is 00100100
If we read 0, we replace by x, go to end hnd 0 and replace by B
If we read l, we replace by x, to end find 1 and B
0 1 xlB
q, (q1, x, R) (q1, x, R) (or, x, -1
(qr, o, R) (q,' 1, R) (q? x, L) (ql B, L)
(q3, x, L)
(q3, o, L) (qr, 1, L) (qo, x, R)
q- (q., o, R) (q., 1, R) (c'' x, t-1 (q5, B, L)

q5 (cr, x, L1

Accept state
B b
Convert the following cFG into PoA:S -) 1S | 1S0S I I (ch 5)
Also show lhat the sking "11101" is accopted by the PoA'
Solution
The language is not CFG so can't convert it to PDA

oofine tho lerms: (ch 4)

i, Ambiguous grammar ii, Parso tree
Solution
t. Ambiguous grammar: A CFG is called ambiguous if for at least one word in the language
that iigenera:tes there are two possible derivations of the word that conespond to different
syntax trees.
I. Parse Tree: Let C = (V, X, P, S) be a CFG. A tree is a derivation (Parse) tree for G it
label e, then n is
a. Every v€rtex has a label, which is a symbol ofV u T u {g)
b. The label ofthe root is S.
c. Ifa vertex is interior and has label A, then A must be in V.
d. tfn has label A and vertices nl, n2, . . . nk are the sons ofvertex n, in order ftom the left,
withlabelsxl,x2,...xlrespectively,thenA-)xrx2...xtmustbeaProductioninP'
e. lfvertex n has a leafand is the only son ofits father.
ulr!l
 October 2016
Theoretical Computer Science

,l. Attempt all of the following: [10r1=101

a {
Stata True or Falss. ls a*b* equal to (ab)'. (ch s)
Solution
False

Dofine NFA. Gh 2)
Solution '
A non-deterministic finite automata can be defined as
I M=(Q.t,6,qo,F)
I where,
i. Q is a finite non-empty set ofstrtes.
ii. E is a finite set ofinput symbols
iii. qo € Q, is start state.
iv. F e Q is a finite non-ernpty set offinal states.
v- 6 is a tansition function that taltes a state in Q rind an input symbol in X as arguments and
retums a subset ofQ.
i.e. 6: QxE-+24.
where, 2Q is power set ofQ

oofins proper suffix with the help of an €xampl€. (ch 1)

Solution
A suffix of a saing, other than the string itself is called proper sutfix ofa string.
Example; x= pqr
Trailing syrnbols: pqre, pqr, epqr
Proper suffixes = ir. r. qr)

Write the mapping of L function in Mealy Machine. (ch 2)

Solution
l.- is a output function mapping from Q x E -+ ),

Give any two idsnti0es of regular sxprssslon. (ch 3)

Solutlon
Following are the identities for RE:
i. AssociatiyityandCommutativity
1, L+M=M+L
2. (L+M)+N=L+(M+N)
3. (LM)N = LO4N)
Here note that LM * ML

0.
T.Y. P-ll Theoretical Comnuter Sctence r
! r 2016 Octobet 1693 ut8t0[
 J,i
T.Y; PdlTheoretlcal' oorprt"r,Sot"n"u .r,f,1411 I october.,' .rv..,, r o. T.Y. Theorotlcal Compuier Sciencb n 3 20L6,October'r, : ,,r- l:.rq,ri r0# i
ur8t0[ ---r$
ll. Distri6ulivity ' ..; ' 2
; :."r
L -i -i?i+i
tr:i
1. L(M +N) = LM + LN Construct a NFA with € moves fortho glven REi'l.0ttoi'tll':+1l,l0r 'i "cll-i:
e {ChQ)

2. (MrN)L=ML+NL Solutiou
r =01(0+l)*+1+0r
oefine Multitape Turing Machine. (Ch 6) rr=01(0+l)r r21110r ._

= t{t
l,;:14,
Solutiotr , . .-1. I .= ir1ff.-i ,.
A multi-tape Turing machine is like an ordinary turing machine with several tapes. Each tape
has its own head for r€ading and writing. Initially the input appears on tape 1, and the others start out
13= 1116 =($+16)+
blank.
ilE &
State tho machines ussd for CSG and CFG. (ch 4) rr= 0
lq=
16=
11*

I !1i';;1ult.?.
SolutioD I5 r6 i'lri:
Machine used for CSG : Linear Bounded Automata 0 1

Machine used for CFC : Push Down Automata Ir,rlt:

Detine ambiguous grammar. (Ch 4) f1
L &".
€
Solution
A Brammar is called ambiguous if lor at least ole word in the languagelhaiit generates there are
rwo possible derivatioru ofthe word that conespond to different synmx uees.
EI
Why is PDA more powerful than FA? (Ch 4)
., "i
'.1
Solution
PD./r is powerful than FA beoause FA can handle only Regular Janguages and PDA can handle
Regular as well as Context Free l,anguages. FA doesn't have capacitv to handle stack whereas PDA €
can handle stack. |, .,'-.:.:
€
Give the regular expr€ssion for the tollowihg OFA. (ch 3)
a

sun 0 e
5 ri,
+: [6*rt*: 'lr
1

Solution
RE lbr the DFA is; l* 0(01)* e
t, t; 6)
.lrl
2. Attempt any two ot the following: 12x.5=1
ri,,i,,i,rfli:l
,i,,;, I'ttl I
Construct a DFA to accgpt the set of all strings ovor t. {a, b, c} such that th€ string starts
I

r=Il+
with 'ac'and not having 'cab'as a substring in il. (Ch 2) i
l
rl = f3 14 12 il: tt ,tttttt.tl
Solution
e

l
 T.YiPJl Theoretlcal Com putet sctence r f,r U9
'201.6 Obtobe1,,;,. ust0r
fp I . 2016 Oclober o.
6;l
Convert the following NFA with e movesto.DFA.
T.Y;'PJl Theoretical Computer sclence
utsl0n

(ch 2)
0 1

a e

Start € b

b €

Solution 1

Transition table 3. Attempt any two of the following:

[2 x 5 = 101
6
qo
b m;Ti_-
,f s-closure (qJ (qoq,) Construct cFG for language L = {anb"c'd'I m, n, r >
0 t}. (ch 4)
q1 o o e-closuro (q1) Solution
{q,}
€.closure (qr) S -+ aSbCDl aAbCDlabcd
o { (qr, 4., q5)
q3 Erlosuro (qJ .{caqJ A -+ aAbCD I ab
d {
o e-c,osuro (qa)
C --r cCD I cD lcC lc
,f d (q3 q1 q5)
qs q5 E-closure (qs)
D-.>dDld
$ {qJ
q5
a
q7 €-closure (q6) {c"}
a I
q7 ,i { €-closure (q7) {qr}
Deflne Type.2 crammar. ph 4)
Solution
Start state ofNFA = qo
i. Type 2 grammars have more rcstriction on the reft-hand side ofeach production rure, that
,. Start state ofDfA = s-closure (qe) ={qoqr)=A LHS is a single non-terminal symbol.
is the

, , .' .i$'[4,p = e-closure (6" (A, e), 0) i.e.c+Bisoftheform

= e-closure (q2) = (qr. qr. qi) = B A+P
6,(A..d) = s_ {qr qo qr} = C
where, A e V, p is string ofterminals and non terminals.
6' (B, 0) = s-.1.rr,. 190) = qo =D tL This class of grammars is called Cont€xt-Free Grammars (CFG).
6'(8, 1)= 0
6'(c,0) = D iii This class generates a large and rich class of languages wlich are suitable for
machine
6',(q l) = o
.6r(D, o) =
o communication.
5'@, l1= q,=E 61(E,0) = g iv Most of the higherJevel Programming languages can be specified using type_2, context_free
6'iE, l)=0 , grNnmus example, C, PASCAL.
Final state ofNFA = qz They are used in compiler designing.
.,Final state ofDFA = q?=E vi. The machine that accepts these class of languages is push Down Automata (pDA)

Trunsition table and tansition diagani

Rowrite the following CFG after eliminating € productions (ch 4)
6 0 l.1l S-+ABlaBb
,
.B B c.t A-+aAle
D 4.
B-+ADlaAb
D
D E
0
D-rbDle
o
Solution
E 0 0
Consider the production D ) bD ls :
Eliminating e

D--rbD b
 o. o.
T.Y. P.llTheoretical computersclence rf r 2o16 october -: ::: '
ut8l0i
T.Yi P-ll Theoretlcal Com nc0 i t, t 201 October I
:
Consider the production A+ aA ] e 4,A. Attempt any two of the followlng! !

Eliminating e a
i
A+aA a Construct a Mealy machino for a language L ovar = {0, 1} which outpub '$' if string sndsI
In production B -+ AD I aAb -+
wlth'aba', outpub'#' ilstrlhg bndd witli'bab', otisrwige (Ch 2) ituhuts'.'.
Solulion
B -+ D Lab ... for A-+ t br
B+AlaAb
SoB+ADlaAblDlab
Removing unit production
B-+ADlaAblbDlblab b

In produrtion S-r AB I aBb substitute A-)E

' S3B lABlaBb
br
Removing unit production a a/$
.1, !,
S r AD I aAb I bD I b I ab I AB I aBb
So final grammar is:
bti
S -+ AD laAb lbD lb lab IAB laBb
4 A b
A-)aAla *"b'c" n >1),
Congtruct a TM for a language L, whero L = {a lm,
B + AD iaAb lbD b lab (ch 6)
D+bDlb Solution
L= (ad,b,c"lm,n> 1)
Construct a P94 ;e1 L = (a'b"c"' 'd';n>l,m>'11. (ch 5)
L = (aabc, aaabbc, aaabcc... ... .. . )
Solution
I-= 13'b"c"*rd' n> 1,m > l) (qr. X. R)
0o
L = {abccd, aabccdd, aabbcccdd ql (qr. a, R) (qi, b, R) (a,.c.R) (qr, B, L)
(qo,b,R) --r error qz (q4, B, L) (q3, B, L)
q3 (q3, a, L) (q3. b, L) (q3. c, L) (q,. X. R)
(qe,c,R) --rerror
qa (qa, a, L) (q,r, b, L) (qs. x. R) (q7, B, -)
(qe,d,R) -+ enor I
qs (q6x, R)
(qo,a,R) -+ (qo,BR) q6 (q6.a, R) (q6 b. R) (q,4, B, L)
I
i
(qo,a,B)'r (qo,BB) q7 Accepl state
I
(qo,b,B) -+ (qr,GB)
(qr,b,G) -+ (qr,GG)
4 EEE
Dlfferontiate between DFA and NFA. (ch 2)
i

(q1,c,G) -r (q2, e ) Solutiotr

(q2,c,G) e (q2,€) i
(qr,c,B) -+ (q3,-) (Q, L 6, qo F) (a. L 6, 9o
(q1,c,B) + crror I 6: Qx I-rQ 6:Qxt, I

(qr,d,B) + (qa,€) One state on one input symboltransits to One state on one input symbol transits to
(qa,d,B) -+ (qr,e) one and only state. more than one states.
(q4,d,R) -+ enor It is deterministic in nature. Itisn eterm inistic in nature

(qa,e,R) --r enor

(qa,e.B) -'r error
 Thoorellcalcom
at Sn tQ,
2016( T,Y. Pll Theoretical Com ter Science . a 2016 October o.
4 A EtrIbolween TM and LBA.
B b
(ch 6) . Conrtruct PDA oquivalent to tho given CFG:
Sdlttron (ch 5)
S-+AA
Production rule ig
A-+0A0 lAl ll
o+ p where Solutior
a -+ p where lol < lpl, Start.symbot o e(Vu E)- and 0 e(Vu r). The ganmar is not in GNF.
does not a on RHS.
UsQd for fecursive
.. Converting rhe grammar to CNF:
langurg;;.
Less than TM Pbwerful than,LBA. S -+ AA Ar -+ A2A2

-nn
4. B, Attempt any two of the folowlngl
[2x5=1
A + 0A0

42 -+ A, I | 0420 l1
lAt I 1 A, + 0Ar0 lArlll
Removing left recursion
! GIE -- 42--;0420 1 1 0A,0 01 10
Convort the following grammar to GNF:
S-rAAla (ch B-+ll1B
A-+SSlb Substituting A2 in Ar
Soluflon Ar -+ 0A20A, | 1A,l 0Ar0BA, I lpA,
i. Substitute Ar for S, A2 for A, Resubslituting by the values of Aland 42
Al +42A2 la S + 0A0A I lA I 0A0 BAI IBA
42 +Ar Ar lb A-r0A0 lll0A0BltB
ii. Consider A1 -+ 42 tr.2 | a i < j lgI1ore B-+ll1B
iii. Consider A2 -+ 41 A1 | b i> j Converting this gammar to pDA
.. Substitute Ar by 41 production S + 0A0A I 0A0BAI I
Az -+ Ar Az Ar,laAr lb 6 (qs,o,S) -r{(qr, A0A),( q6, A0BA))
Removing immediare lefl recursion
S )IAIIBA
-+ aA b AA is in GNF. 6 (qr,l,s) --+{(qr,A),( q6, BA)}
B-+42ArBlArAr A)0A0l0A0B
Substituting 42 in Ar
6 (qr,o,A) ---+{(qs. Ar),( qp. A0B)}
A1 -+ 42 42l a
A -+ lB I I
-.l aA aA b a
6 (qr,1,A) B),(,qr.e))
Substituting 42 in -r{(q6,
D B -+ lB I I

+aA aA bA aA 6 (qp,l,B) --+{(q6, l),(

9o.e ))
Resubstiture Ar by S and A, by A PDA is
S-+aSAlbAlaSpAlboAla 6 (qp,0,S) ---+{(qe, A0A),( qo. AoBA)}
A+aAlblasplbp 6 (q6,1,S) ---+((qq.A),( q6. BA))
B -+ assp laSp lbsp lbs laspsp 6 (q6,0,A) ---l{(q6, Ar),( qo,AoB)}
lasps lbpsp I bps
is fmal production.
6 (q,,1,A) ---+ {(q6, B),( q,.
e)}
6 (q6,l,B) ,+{(qq, r),( q6.e)}
 T.Y. P-ll Theoretical Computer Science a r 2015 October ' April2017
B c
Minimizo the following DFA: (ch 2) Theoretical Computer Science
M = ({90, Qr, 9a gr, 1 6, qo {q2, qa]) whero 6 is giyen by: i

+qo
6 0 1
'1, Attompt all of the fotlowlng; l'tO x 1 = {01
Qr 9z
IT:a I
9r 9r 9r
Define regular oxpression. (ch 3)
Qz Qo Qr
q1 qa
Solutioo
Qr
*qr ql A regular expression is a set of pattem matching rul€s encoded in a string according to certain
Qr
Sohtion syfltax rule. i
I
I
9r x 1 b
Glve the mapplng of'6' function ot NFA with € moves. (Ch 2)
q? x X
Solution I
er X x i
6 is a aansition functiolr for NFA with e moves
q. x x X 6: Q x (ru {e })-+2a
qo qj q, q3 q. . The intension of Q x (, u -r 2a is ftat 6(q} a) will consist of all states p such that there is a
{B}) I
I
transition Iabeled a from q ro p, where a is either e or a symbol in E. I
[qe, q3] are equivalent and [q2, qa] are equivalent
1 c I

0 lfA = {€}.Find tho value of lAl. (ch 3)

Solution
l
lqo,qsl lAl=0
I

Which tool is usod to provo that the languago is not r€gular. (ch 3)
0 Solutior
Pumping lemma is used to prove that the larguage js not rcgular

Dittsrentiate bstwedn Moore and Melay machine. (Ch Z)

I
Solution
0
h Moore machine the output is given at each stage and in Melay madrine the output is given at
Bach transition.

o" Give the language accepted by the following FA. (ch 3) j

utSt0lt

Slart

b
a,b

Solution
aal(ab*aXb

I
T.Y. P.ll Thoorotlcrl Qomputer sclencc . i . zorrepar l1@ urf,in
 T.Y. PJI TheoreticalCo m uter Stllencel t 2017 o' T.Y. P-li Theoretlcal Computer Sc i"n"". a).
Esl
Dgrine Kleeno closure. lllr
[|'. 2017 April ut8t0n

Solution (ch 3) Writ6 a language for CFG: (ch 4)

Kleene Closure (Kieene Star): The Kler:ne closure (or S -+ asa I bsblalbl€
closure) ofl, denotes Lr is the set.
Solution
L+= u i Language for CFG is
i--0 The set ofpalindrome strings over (a,b).
L*= el'l
Kleene closue is concalenation of zrro or more elements with itself. It is a unary opemtion 2. Attempt any two of the followlng: [2xs=101
introduced by Stephen Keene.
EIal
C9ryy9l DFA to accept the set of a strings ovsr I = {0, 1, 2) such that the string ends
Writg the tupls oftliring machine "
wilh '012' ot '20'.
Solution (ch 6) Oh 2)
Solution
A turing machine is a 7-tuple. 2 0
M= (0,I r,6, qo, B, F) whae, 0 1 2
l. Q is a finite non empty set ofstates.
ii. I is a finite nonempty set of tape symbols.
iii Be f is a special
blar* symbol.
iv. , is a non€mpty set ofinput symbols and is a subset ofr and B e X. 1,2
qe e Q is initial state.
vi. F q Q is the set offinal staries. Corutruct a FA for the given RE: (a * b + b " a).ab +ba.b* (ch 2)
vii 6 is the bansition firnction maoning the states of the Solution
symbols and rhe
* 'FA
'.
r <ie
and tape
svw symbols
J.,trru to states, tape r = (a*b + bra)ab + bab*)
mover",rt ofthe t"Ia, i.""
6: Qxf-+QxFx[L,R] r1 = (atb) + b*6)61 12 = bab*
i.e. the value of6 (q, x); ifdefined, is a triple (Pl, y; D) where rl = a*b + b*a 14= ab
a. P is the next sta&j in 15= a*b ro= b*a
b.Y ef, wrirten in^theQ.cell being scanned. relrlacing whatever symbol was there. rt= 14 ra= b
c.D - or('ctron: Left or fught. tells about the d.irection in which the head moves rq= b* rto = a

Write lD for PDA.

Solutiotr (ch 5) rlo=
In FA, ID is defined as cunent state. of
proc€ssed to describe the finite state
machine.
FSM at any time and the remaining i/p string to be @-j-@ @-r@
In PDA, as. we have stack, we need to specify the current state, a r
remaining i,/p string to be
processed and the symtrols on the pushdown
stack.

:.If Y = lO, ,, f. 0, qo. a,

xeE*andd€]-*
F,) is a pDA, then an ID is (q, x, o) where qe Q,
i.e., q is cunent staie. e

w is input left to rt:ad.

is on stack (firsr symbol ofo, is lop ofstack).
-^-o
llM = {Q. t. F. 6. qe, 24. F) is a pDA. we say (q. aw. Zo)
F_ (p, w, po; Is=a*b 16-b*a
if6(q. a. Zr conrains (p. g) a may be r; or an i/p symbol.
i.e. Ifwe have a rransition 6(q1. 0.
G) _+ (Cr, ic) rhen (q, 011, GCR) f_ (q1, I t, BGGR). Qs.
€
9c
!
@
 . o, o,
T.Y. Pll Theoretlcal Computst 2017
T.Y. P-ll Theoretical Com sci€nce 5 ) 2017 A utEt0t

rj = rr+ 16
Let qo = A be start state of NFA
.'.''6 (A, 0) = qo = 1
€
6(A'1) =q,=B
6 (B,0) = {q,qr}= C
6(B, 1) =ql= D
E (C,0) = (qo,q,) = C
6 (C, 1) = q,=D
D (D,0) = q,=3

11= I]t]gls 6 (D, 1) = {q,,qr} = E

6 (8,0) = {qo,qr} = C
E
Qg 9z Qs 9o Ts 6 (E, 1) = {q,,qz} = E
0

1
12 = bab*
= r8Il0I9
0
0

r3 9o Qz e: 9o
0

r=rl+12

'. Final state = (D,E)

3. Atte any two of the followingr [2 x 5 = {01

E;I-l
Construct cFG for language L = {a"bmcmd" I n > l, m > 1}' (ch 4)
Convert the following given NFA to DFA. (ch 2)
a b b SolutioD

Sta.t b a
L€t G = (V, P, S)
', x = {a,
v = {S, A), b, c,d}

b a,b S is start symbol

Solution Pis:S+aSdjaAdlabcd
Transition table A+bAc
o
a
qc
b
qr
3Er lbc

Congtruct CFG for language L which accopb set of all palindromss orsl p. b}. (Ch 4)
{a,
q, {q"q,} q?
SolutioD
q, qr (o,,qr; To constsuct grammar G, all the above tluee rules can be used.
a b b Let G = (V, E, P, S)
b a
From (i) S+a, S+b
From (ii) S -+ e
b a,b From (iii)S -+ aSa,S -+ bSb
Taking all together
V= {S}. I = {a. h} P= {S -l :q, '1"'' '! , '
 T.Yr PJl Theoretical Corn utel Scfencer 2017 T,Y. Pll Theoretical com pute.Scie.ncet 2017
0:
A b
Rawrite the following CFG after ellminating .
uselesg symbols: (ch 4) , too 1o, 1 {0n1"2"0'I m > 1,n >{ }. (ch 5)
S --r 0A0
OD
A --i Sll lCCl DOA
6(qo, e'R)- ERROR i{{
C-r0lllDD 6(q0,2, R) - ERROR
E-+0C 6(qo, o, R) -+ (qo, BR)
D -+ ODA 5(qo, o, B), -+ (qo, BB) 6(q,, 1 G) -+ ERROR
Solutiou 6(q0,1, B) -+ (q,, GB) 6(q2, '1
G) -+ ERROR
In the given grammar symbol E is useless as it
is not reachable &om any production. 6(q,,'1, G) -+ (q,, GG) 6(qr, o G) l ERROR
If we start aI stafi, we can not terminate the grammar
i.e. no terminal string generated from 6(q,,2, G) -+ (qr, e) 6(qr, z B) -+ ERROR
ammal so the grammar itselfis useless. 6(qr,2, - G) (qr, e) 6(qz, e, B) -+ ERROR
6(qr, o, B) -+ (qs, e)
Construct a TM for L = (wcwRl w E(a + b).) 6(q3,0, B)- (qr, e)
Solution
(ch 6)
6(q., t, R) -+ (qr, e)
The TM is 6(q,, B) -,
e, ERROR
6(q,, o, R) -+ ERROR
(oo, a, n1
(qr, x, L)
(qo, b, R)
(94, x, L)
(q,, c, R)
[a EE
Dofl no
I

Recursive language. (ch

(q3, x, R) 6)
(q| c, L) (qr x, L) ution
(q/ x, L) (q., x, L) (q3, c, R) (q3, x, R) (qs, B, L) A language L over the alphabet f, is called recursive if there is a turing machine T that accepts
(q3, x, R) (q., c, L) (q., x, L) every word in L and rejects every word in L' i.e.
,c,L) (c., x, L) ,B,R) Acc?t (T) = L
Accept state Reject (T) = L'
4, A, Attempt an y two of the fo llowing
A a
[2'x 5 = 1 0l A I
Construct a Moore machin€ for a tanguag€.L olfferentiate between recursive and recursively enumerable languages. (ch
over, = (0, 1) which outputs ,g,'li sirirg en6s Solution
--*' - --
6)
with "t00', ourputs,#'if string ends wii'h'o-0r,, ottr"rw:ise;ltpl;':;i"
ie;:;) If a language is regular and we have an FA that accepts it then, if we are pr€sented a string w and
Solution we want to know whether w is in this language, we can simply run it on the machine.
Since every state haisition takes up a letter from w, jn exactly length (w) steps we have our
0
- yes (ifthe last state is final state) or no (if it is not)
answer
This is called as effective decision procedure.
If a language is recursively enumerable (r.e.) and we have a TM that accepts it, then if we are
presented a string w and we would like to know whether w is in the language, its tough.
If we run w on the machine, it may lead to HAL-I dght away. On the other hand, we may have to
wait, We.may-have to extend execution chain too long. Even then, if w has not been aciepted or
rejected, it still eventually might be. In worst case, w might be in the loop set for this machine and
shall never get an answer.
A recursive language has the advaniage that we shall at least someday get the answer, even
though we may not know how long it will take.
1
We can sa, that
Not all rM's that accept a rscumive language have no loop set. A language is recursive if at
least
one TM accepts it and rejects its complement.
Some TM's that accept the same language might loop on some inputs.
 T.Y. Pll Theoretical Computer Sclence | 20'17 A
T.Y. Pll Theoretical corput"r S!-1"na".,f,o 20l? April
o.
utst0i
ffi Substituting A.2 in Ar we get
4. B, Attempt any two of tho following [2x"5=tOl (.
Ar-+Ar&lArL4ll
4 a
Convert ths followlng grammar to GNF: (ch 4) -+ lA 1A 1 I is in CNF
S+ABIB Substituting Ar in
A-+BS
B --rA111 0 + lAr A: lDAr Ar & I lAr & Aq I lPAr A A
A,{ I I lA{ I lA' A3 A19l10A'
Solution llA,A{A..pll Ar A A.1p I lA.. p
i. Thsre is a unit production S -+ B. Removing unit production, the gfa4mar is The grammar in GNF after replacing by original non-terminals

S-)ABlAl 11, A-+BS, B-+All1 S -r 1SB I1PSB llSC' llscr llpscr ll

A-+lSIlps
ii. The grammrr is not in CNF.
B+1llp
Converting the grammar in CNF
Cr-+1
S+ABlACr l, ArBS, B+ACrll, Cr-+l p C' I lpscr Cl I lCr ISBCr p I lpsBcr p I
Replac ing S by A,,
-r ISBC1 lpSBCr I lSCr
| lSCrCrp
llpscr cr pl lc' p
bY 42, B b
B bY Ar, Construct PDA equlvalont to ths givsn CFG: (ch 5)
cl bY A.4 110i1!i
S+aAblaS
Ar -+ ArAr I A2& | 1, A2-) Ar Ar,Al-+AlArl l,Ar-+ I
A+Bbla
B-+Salb
iv. Consider the production Solutioo
Ar-+A2AriArfull i. Converting this to GNF:
Here l<2(i <j)
Ar -+ aArblaA,
. . We leave this prcduction
v. ConsiLler the production 42-rA3bla
42 -+ 43 41 A3*rAlalb
Here 2 < 3 (i <j) . . leave this production. A: -+ aAzbl aAralb
vi. Consider the production
Substituting Ar in A,
Ar+A.2A.4 l1
Here 3>2(i >j) Ar + aArbab I aArab I bb I a

.. Substitute A2 productions in 43 Resubstituting

.'. 43-+ArArAall S+aAblaS
Immediate lefl recu$ion occurs. So removing left recursion A-+ aBbab I aAab I bb I a
B +aBba I aAa lb
Je, -+ r I rB is in GNF

prAr ,\ ArA.ap Converting this grammar to PDA

Substituting Ar in A2 we get S -+ sAb laS + 6 (qo,a,S) ---+ {( qq Ab),( qo,S)}

A2 +A3A1 S+aBbablaAabl a + 6 (qo,qA) --+{(qo. Bbab),(qq Aab)( qr,e)}

li A -r bb :+ 6 (qn,b,A) -+ {(So, b)} I
A2-+lArllBAr is in GNF
B -+ aAzba I aAra + 6 (qo,4B) --+{(q0, a,Arba),(qo.a3ra)}
. B -+ b +6 (qo,b,B) +{(qo,e)}
 T.Y. P-I reticalCom Aprll o.

Minimiz6 tho following DFA:

(ch 2)
M = ({90,9r, Qa gr, 9s,9 1 6, qo (qr)where is giverby:
6
6 0 1

-' qo Qr r.t0
!q, 9r qo
q, ql Qr
ql
qa qo
qr qr Qr
9o q7 Qr
Qz ar ql
Solulion
,
qr X
i
q2 X X
q3 X X X

qa X X X
qs
X X X X
q6
X X X X X X
ql X X X X X X
qo q1 q, q3 qa qr q6
'. [qr, qo] [qo, qr] [q2, q5] are equivalent states
0

0
lq3,qJ 90,92 0

i,

lqz,qJ
0

o,
r,!sr0fr
 B**1e
tS
\,r'

de-finitio:
L
ct linite st at€-s
lC(r iillJUL .lllJl ldUet.
led o,"r'rout a lpha bct
lnifia! rlate rvhicir is in a
T
a Ut.r,,t svmhol (Cenc
)f final states a \ Ql.
rrE!i;i-n--g--T-rcnrqJ_!.r_q
The a Lrove nlacLitl(r grafhtca ly represented as bclov\
nr-r', rl /.)LrtDUt taDe
-, -r-r-I.
l

In cr(- rr r:vq (l vement) of rcad-v,rrite head foiioi

aracter fronr the cell.
Clt; state from on( to o!:rrcr state
ii;-r I ir.lrr-rr svill:ol b" soilre 911161 .,synrbol (
.',-i,,

t l€rzog n tze
Pet ft>rft
the
c.r r
t o^q '
prfnajjC t5\ob leo

rf be-t oJb I ) I {\ D.rtd

"+{tte 5
 t
{ o ,lYl ochrne. r.uiHnout O l4crchrne urith
r*
i
cnemors rnef,nor\ (5+ocg

lD 0 Fq is leos pouerPo.l @ I4ore, pouerRrl

ii)
ts
@s tuppte o ,f ,d, 9o, F @o(+,E,r',dolooP.,
Cornnarison with other Machine: to:)
P
I
Sr. Finite Automata
i
Push own Autom ata Turing Machine
Iu No.
1 It accepts only regular
languages
It accepts reg u la i- It accepts RLs, CFLS as
languages as well as ( Cf1) well as Type 0 languages.
[-$ Context Free Lan UA es.
2 Tyes: Types:
l-$ FA without output - Sihgle stack PDAS:
Types:
.DTNI, NTM,
(DFA, NFA)
IE NPDA, DPDA, Both are sub
e I
M ulti tape Tt'l,
nto two categories: Both ended TM,
FA with output
fo (Moore, Mealy)
fqoDra rnochina_
- accepted by empty stack
and accepted by finaT-
Single e nded TM,
U n e rs a TN1 H a n s T t'l

1s rneuhq rnociine. state.

-Mul_-ti stack PDAS.
[."
3 NFA can be converted to NPDA can not be converted NTI'I can be converted to
r$ 4
DFA
Limitations:
to DPDA.
Limitations:
DT[4.
Advantages:
[-e ) It can not recognize ) It can not recognize 1) It can perform all
lang uages with equal a ng uages wi th equal
Is number of two or
more symbols,
number of three or more
symbols, palindromes,
arithmelical operations.
2) It can recognize all
strings.
[{t palindromes, ba la nced
parenthesized strings
balanced parenthesized
strings
[-* ) can Lgt perform
It It can not perform
f" arithmetical
o eratio n s
Ex (Applications):
arithmetical operations

Ex (Applications):
I
D"rForn

Ex (Application):
ID Text editor, . I
Parser used in HLL Computer

l" Lexical Analyzer

used in HLL

fD Exercise :Construct TM for th e followin

L={a'fn/ n>=1 )orL={a'b- /n,m>=1,n m)
<b,b,L)
["-
--.B {;=*,-.o
[*
['i; =*-
["i ) L={a'b'/ n>=O}
)
fu D !- 1Rl

IF]
3) L={a'b'/ n)=2}
t: 2--\
131-r-- <b'B'L)
-_ - - =-)
.,
F
I

Iir __J
It.
l+
 v

c
s7) L={ aib"c"/i,n>1,i<n)
a'bncn 7 irn > L, i <= n)
s8) L={ ib"c"1i,n>1,i*n) e
se) L={a c

Non- Determi n istic Turing Machine:

(P Fll'l) (
When there is at least one trans ition function 5 defined as
5(q,a) {(Qr,Yr,D' (qr,Yr, Dr), (q3,Y3,Dr), (qk,Yk,Dk)) I
for some state in Q and symbol a in >, then the designed TM
q
(
is called as Non-deterministic Turing Machine (NTM)'

In other woids (
head move)
The NTM has a finite number of choices of next move (state, new symbol, and
if any of choices leads to an ID
for some slate and symbol scanned. It accepts an input sequence (
with an accepting state.
(
T es of Turing uachine)
m Pos ur ng a chine:
s )
need to break the I ive n p roblem into smallest problems such
solving each o f these smaller P robl<ims, byusing the answers of one problem as the
input
that
data for second, we can arrive a t the fina I a nswer]
To obtain the
A simi ar pioceZu re can also be used in th6 d esign of the Tu ring Machine.
will Ee-comEineo in
solutiort we nlay combine two more Turing Machines. These Turing machines
suc a way that qtput o-|![el!!sJ Tl'1 is input to the second,
the output of second TM is input to
as Composite Turing
third and so on. Also each TM is solvinq a sma Iier problem. This is known
Machine. the
Cil. .rr.of while finding GCD of two unary numbers CTM uses different TMs for copying
numbersl-\
\ffi;, ilHt.g ", ,";"i;o?,;[rr-tne rre]p oia series of subtraction of two unary

(-2) tterated Turing Mach tne: .oute.O

L- In this type of mach ines own outP ut is treated as in ut to solve IVCN

P Universal Turing Machine:

A TM, with the capability to solve anY P roblem by properly adjustinq
re presertta tion, we can use it to comPUte !-ry
a Tu! ng-qqnuulq B le
the input
function that is a ny other
UniveiisaTTU
by othe r Turing machine, is kn own as n-g
function that can be computed anY
-maahinE. \ Machine with the
The!-niversa I Turing Machine is caPable of imitating any other Turinq
following information on its taPe:
ih; "d eEe1liq! qi r! a lein's ol t9 -FM (This part of the tape is called alplpqlq rrle rr?9 ) '
")
b) lnitial configuration of TN{ that is the starting ot the current
state and the symbol scanned'
(This will b e the state area of the taPe)

c) The processing data to be fed to the Tf4 (This wi ll be the data lape)

C-a ) rurins Machines wit h Two Dimensional TaPes:

one read-write hea-d and one
L-- Cthis is a kind of Tu ring mac hines that have one finite control,
end an elefte nd but extends indefinitely to the
twb-dimensional taPe. The tape has the top .rall
sd ividedlnto rows of sn squarPs. For anY Tu ring machine of this tYPe
ng t an own.
e nElonafEFe that is equally powerfu!, that is, t hc
tfr-erE E a T-iing mach lne wlth a one
former can be sirnulated bY the I atter.
To simulate a two dimensional taD ith a one dimenslonal tape, first vJe map the squares
tape diagonally as shown in the
of the two dimensional tape to those o f the one dimensional
following ta bles:

Page Nurnber: 93
I

I
{}
il
i

I
I
I
D
I

D
I Two Dimensional TaPe
I
D VV
I
!
I L4 L7 26
t h 9 13 i - 18
*-f- t
25
l

S h 72 19 24 f-" .".-.1 :.
h
D tt i zl , )2-i T- I
r I

i Here the numbers indicate the correspondence of squares in the two tapes: square I of the
two dimensional tape is mapped to square i of the one dimensional tape. h and v are symbols
-\il which are not in the tape alphabet and they are used to mark the left and the top end of the
t tape, respectively.
'-s
One Dimensional Tape:

[{s le [o,Rhi,[- l. - |

The head of a two dimensiona I tape moves one uare up, down, left or right.
Let us simu a te this head move with a one dimensiona I tape
['* tape. If t ad moves down from i,
Let i be the head position of the two dimensional
[** then move the head of the one dimensional tape to right until it hits h or v counting the
i. the of squares visited by the head of
[.r number of squares it has visited after Let k be number
the one dimensional tape. If h was hit first, then from h move the head of the one dimensional
tape further right to the k-th square from h. That is the square corresponding to the square
[.i below i in the two dimensional tape. If y was hit first, then (k+1)-th square to the right from v
is the new head Position.
[.* For example, suppose that the head position is at 8 for the two dimensional tape in the
above table, tnit ir i = 8. If the head moves down to position 13, then for the one dimensional
['= tape, the head moves from position 8 to right. Then it meets h first, which is the third square
from 8. Thus from h, move 3 positions to the right. That is the head position of the one
['* dimensional tape corresponding to 13 on the two dimensional tape.

l" If i = 5 and the head moves down on the other hand, then on the one dimensional tape the
head moves to the right and it hits v first, which is the.second square from i = 5. Thus this
time the third square is the head position of the one dimensional tape corresponding to 9 on
l'* the two dimensional taPe.

lc, similarly formulas can be found for the head position on the one dimensional tape
Ir' corresponding to move up, right or left on the two dimensional tape. Details are omitted. Thus
some iuring machines with a one dimenslonal tape can simulate every move of a Turing
lr'
t
machine wi[h one two dimensional tape. Hence they are at least as powerful as Turing
machines with a two dimensional tape. since Turing machines with a two dimensional tape
obviously can simulate Turing machines with a one dimensional tape, it can be saiC that they
[" are equally powerful.

Machines with Multiple Tapes:

["
E Turing
This is a kind of Turing machines that have one finite control and more than one tapes each
5 -tupTefq, : I', ,I nsition un otl
with its own read - ite he ad. It is denoted by a Qo, 6 S ra
["=
Ir:
I
tL
rs a partial f unction
Q x {H1, H2, Hn) x (rw {a}) )(Q u th}) x (ril t^})" x 1n, r, s1",1
A config u ration fo r this kind of Turing machine must show the current stare-the machine is
[.' in and the state of each tape.

lu' Page N u;nl-.er: 94

li
t ..
 c
3otvc^ble + u^soh/r^bla' lrTob 6- lr I . booh
I
e.

it can be proven rhat anyl":f.,?;i1."T?:""r.i,J""1il;",?:.til:t"T.i:?':?iiffi:[",r:".t":' a

; one tape Ttrring machrne^"];,;;;;.'ni;".-since the converses are obviouslv true' one can
;";; ;; i' n-tu p" ruri n e m ach i nes' €
:"' ;;"": ;
::,':#?::""',:',: ff;'ff H":ilil]
Heads: )
frr-ri"s Machines with MultiPle
,-v \_{rhis is a kind o f Turing machin one finite control and one
es that have
taPe
to read a
but more than
nd write. It is e,
hea ds. In each state onlY one o the heads is allowed
on&rea d-write is a Partial function
(Q, z, r, q o, 6). The trans itio n function
denote d bY a 5-tuP le h)) x (r u {a}) x {R, L, s}, C
H2, . Hn) X (r,-.' {
d Q X {H1,
, Hn denote the ta
^)))(QU{
pe head s,
where Hr, Hz e,
powerful as one tape Turing
easily seen that this type of Turing machines are as 6
It can be
machines.
c
which extends
one rinite contror and-ene lerre
"tfl+l?,tT11tr",1:,ll#t#:t:J"1'#ave 5
as one tape rurine
4t:lll?H**m3?#", rurins machines are onty as powerrur t
*hot"
.uaf in"t tuP" has a left end'
(
tJ" :I^".ll:'t" contror and -one !up' yhi:h extends
" '"'+l,n T';lilr"'"r1'il"t"il*il,l+Hj[ iiir' no i"rr5 to the 19ft!f the initial
infinitely ir{-one directiihat
is infinite
"U491!!l'9i;
head Positibnl-
-
Limita tio ns of Turing machines el the strengths of a Particular
of Turing Machi nes is that theY do not mod are actua lly instances
,-) AI imitation
modern stored-Program com uteri
p
rran9e ment well. For instance, access stored Program
a
machine known as the ran d om
of a more sP ecific form of abstract
model well For
machine or RA SP machine is that theY do not m odel concurrencY
of Turing machines an a ays-ha Iting
Another limitat ion of integer at can e
is a boun d on the size
examPle, there starting on a b lank taPe.
nondeterministi c Turing l'4 achine ower. To overcom e this limitation
we use
?\ Th e basic mod el has no com U tational
i
-tape TM, m u lti-head TM, etc'
u?r-omp osite TM; iterated TM, mu mber of states is restricted, and then we
need to use
4) Size of ta e alphabet or the ntt
different Tu

Lan ua es:
€ ages ls

oft
Th
Th over the
1.

,'aH*e,' *###T !:gr

presented w'th:;
Je! y: I :' :,.
:
I

ini;"si'iig'
s
nuttI l'fl :::::,"i
una^uc-cept it tl'" ".
the string is ilin TI
JilI,', the i:language'
"!'''
^
will. when
,ndhultandrejectotne.*irl.t'd"iriing?.r.r,ineatwiviharts;irislinownasadecider
Ini it.uia rc decide the recursive language'
enumerable' All regular, co ntext-free
and
also recursively
No te: All recursi ve lan UA es are iuu
ext-sens itive lan guages are recurs

Page Number: 95
;*E-$

lz,

$
D
r.)

d ecursivel Enumerable Lan uage:

ls a so ca e ecida e Turi ng-acceptabl e. It is known as a type-O language
o in the Chomskv hierarchv offorrnam norraoec 11," 61il-nFall rprlrcirrehr an,,m6r.hl^
languages is called RE. /
D There exist th re e Eq-iffiTE nt major definitions for the concept of a recursively enumerable
language.
o 1. A recursively enumerable formal language is a recursively enumerable subset in the set of
all possible words over the alphabet of the lanOuage.
! 2. A recursively enumerable language is a formal language for which there exists a Turing
machine (or other computable function) which will enumerate all valid strings of the
E language. Note that, if the language is infinite, the enumerating algorithm [rovided can be
chosen so that it avoids repetitions, since we can test whether the strinq pioduced for
D number n is "already" produced for a nrrmber which is less than n. If it already is produced,
use the output for input r+l instead (recursively), but again. test whether it is "new',.
{, 3. A recursively enumerable language.is a formal language for which there exists a Turing
machine (or other computable function) that will halt and accept when presented with any
$ string in the language as input but may either halt and reject or loop forever when
presented with a string not in the language. contrast this to recursive languages, which
S require that the Turing machine halts in all cases.

(l Note: All rgqular, context-free, context-sensitive and recursive languages are recursively
\'-enumerable- \
)-"
D 2-4-4 Flectrrsiwely Enurnerable Languages -Lpp
In this subgcction, y.c 6hall study l;rngu{ges a-*rocis,tcd *'ith 'ntring msahines.
$ Definition 2.{.8 A l.urgrrag€ , over &rl inpu! slprratret E i6 said to be r.-
crrrsiuclg eaur*tttble, deooted by Zar, if therc exists n :I\rirrg Inaahillc tlat
D a(cepts it. ll<tursiwcJy enurD(:rlrt le hlguages arc also calle<i Ttirtg dcccptablc
langtagcs, or Tiring recogaisablc langtage-l
b Dei-Bitiott 2,4.O A l:rrlaulr{ie tr over en iuput alphabct E is said to be r€crr-
riuc, deaotrd by lnt:c, if therc cxist-s s I\ring rntr hinc that lcccpts .L, and th^t
D lrrrlts on er.ery inprrt r, € tt. Rccursii'e lnnl4rrageri 6,r€ al6o called Tbiag decid-

t ablc langtrcgcr, or recursii'cly decidable languagcs; rl'e shall discuss tllc concept
"dccidahl{ in Chaptor 3.
TLc terh 'r'Ecurriucn comes frotn the theory of re'cursive functions. It G
B clcar thst ! recursi!.c l&oguage i! a.lso I recursively cnurrrcrablo, lrut on tlrc other
hs.nd, a rccursiyely enunrctatrle lalgrtagc is rot n.lcassarily rccu.$ir.c. That ls,
e No C*rg '@&!a Ae.p.ln8 M*hltE

D ]t.er,.&l r,,
(1ui6s Mr}i,a)
T!"1 Gd.r.r Lu*uir,€
(No Cl.{rB.icd Rul€)
3 T)'rE O 1..{au.{<6 are
(TyI,c O Groru Cpsl

\i Acapt6d l,y LBA -

-- Trtt
(irp.
1 tff6!.xt5
I GrMhd.
i6
C(s)

r* "ryrt 2 l;bAu.€d ,ry

(-ryp. 2 airerhrr! c<is )
e
'ryr* t t,.ngtrlsd ,&e
a A<rpt-I b, nDA
(PEtlD@D AuLom.tr)
(Trp6 a Crunm.a (?^E)

U
0 (Fi6ircstlt. }\u.drEr.,
FigllE 2-r9: Eicr..clitc.l ll.lall6ns b3!*'r,'r \r'tiou5 LsrsxlaBlcrtDEl'B'd
b tb€i' Acc€prina Ma.)ria€

- Page Number: 96

Ei'
 rs said to be decidabre'
ransuaee s rocursive
G.tid'Xl;:;,""H"f,t;"
problem: said to be-undecll,"^bl:"1:J-t'"txT:ff[,t""t
undecidabte ,-6^,.>.1p is r.ror recur-sive is

:i
g:
i;i: ul "; ;:i ""? """ :'
$;[#ii:
"':L:''""
.-0,*'"1,il.?i:i".-:".,..,*:1,:lli:!:?l',:l'111:,.T"]}*;ifl*[l#.il;;l*Hi-ii,{#:t
r.t hcr thc pro sram' !" 11;';l ::iJ="." ih. p,o g,u'n * ilt
lrct
and xl'l ll I
given a Progtrtn
s ill run lors 5
LBA and CSG:
I ntroduction to
<191andct'9 (V U T)* one more
cr)Fwithl
rules are of the formppear on R H S. of anY Production '
Th e produ ction not a
sta rt sY mbol 'S '
does
restrict ion is the ion as only S)e not
A)e
ause the pro ductions a re of
the form
o2
We can write Product is called as context sensitiv e bec in context 01 &
This g ramrnar tofA is allowed bY P onlY hich is
aZ (9+e)m eans rep lacemen "Context S ensitive languages
o1.A. n2 => ol..P. called as
generates a lanqu age Autom ata (LBA)"
The g rammar as "Linear B ounded
ne called
accep red by a machi P where
, A)
e.g. G ({ A ,8, C} , ta,b)
P {A ) ABb
ABb , ACb
Cb ) abb ,)
the
ata (LBA): Turing Machine satsfying
near Bo unded Automa utomaton ( LBA) is a nondetermi
nistic
q" Ali near. bounded
llowing two conditions: includes two special sYmbols c
a nd $, the left and
right end-markers'
1) Its input alPhabet over c or
nor may it print another symbol
' from $'
res PectivelY left from c or right
2) The LBA has no moves
$. imP- r, 6l :-9 "
M :,f 5 0, c, $, F ), where a, I, ":1^t.1'J"?;j"'
resPeL,v)
AN LBA will be
denoted
s in e e lnd right end-markers'
TM; c and $ are sym o
non-determini stic

Page Number: 97
 G)
Ul N o+ q\nfiipbv uJ e
UJO 3 *,.rm gJN
Q 'v, q' b Q'Y
a6 ob aIofs lfo pu.r3 )
,b
? qmc!.Htrn UJN ?Ja^\r9O (
rtdo.t+st- UJN tr o? ?A/olp^rn@ UcO 0 -,'1

+l S 1"1 I aBon0uot uo urdo (g

' r r3ord {rr^
uarTotal (e
,arnpord \totsol3D) (Z
'?os Uo urdo oo+ FuU <r-a
Elroel alr uolpnpotlul1
9tl
 O Qn'te BuLomouo .

k _. _
- 1}a connPulsonl
upples of q,.cg froit€. Rulp mcl.to
5- ru,optes
m= l0,Z,clogo'FJ
urhqe q = 6a, Of SUrt!€
Z = Se.t, o{ input cjPhobets
d= tronsibion' f11o
9o' iniuiol stcrte
f ' fincrj sttrt€
$Flq {or sJ I €+t s brpples cu-e scilrr'€ onry
trorsition fuq is diFcaJQnb
ocR I d=OxE-->O

NFff C+ d: q XZ-+zo

NFfl tuith e d = eXtEuej+z

NOEq\
OFe Con nevar hqS e rroyAg,
Everv DFR iG NFf\ bu-t eva-r! NFR ls noL
opA.
. iF Cons1'ruclion of OFq r- 5rn & lrn. BaO.
r> 5Lo.rt tliLl^r
r) Tt hqs gerror Ststp. in VL
2> [.,usu su].t€. +e'rnsfer crl I

S) =L
9eno, ho{ o,Br aJl State cve. mo\re-
q-) .- obc

2> Subsr+ing.
r1 No Q€fror SRLE-
)i.],put,
>|. Final s+o.Le rno\r.eJ cill efPlah s+€J+
g) '

-obs
s> end t.,.,lt{r .

r) No qerror s+ctg
-) {inal alalg nol rnov€l oJ, S+tttainPuL
s) ab c
*) chqck cr.6 Ev : b1C bocq
boc b
bqcc
€rrnerr fod cf: rrttnsfirlg o's b'3 Ernl
o
e PvQ6 Q!€, Qo
b
\b b evzn o dcl Qt
q_
arb
Odc/ ovqn It
d- odd odd 4t
o. [o.u,cJ sucn bhoL sring bub ct
Subsxing t encl turt-h bbo
bqn nbc.
bona.
d rcrut o5D-sJO-LC 9+
than 6ep,c^Iurc d rour end in j
tlren cornbine oor-qh olha.r .

O. tuhe^ or is w€
lol or llo'
rrconvcrslor oS NEA to oFR toEA equivu]e^t
tY Ftotn dtoq- Or toble-. lo NfA)
,> Orutrt \*onsiHon tfilDlO
cy .Tniuol str'.ts + nd thQ^
+) heut Slcrtp- Ocrufed fl,i: B =

I t*'cn find urhan thaq s+cp to occ,)ftrl

rEf€ot,.
6t Srow d iog
nQrlJ St'[l3e' tnc]\rde'
:ry Iro.q t{unsiHon {eble trofoPle}e-/dM'
oJl tfunsocHtr''
tr'nc^l Sl€rfp, r s -tu{ l-h'e sk}tP'' \r]hlch
. ") inctucle, ioiLfoJ S+ot€ is Fintod
 A.- Conr"rb Np4 wilb € ilos+e ornre^,@ '' '
NFR tlifirau*- G
t) find € closwe oI olr
srcr.to
e) Inrbiol stctte-
g) find oJ r d'C ) ol I inputJ
$) Sruur di u$klrn

^zQ
NPA wf h € utlbh APfi
l) Frnd+ o.lt 6 CJoSU/v-
) inlfta-l Stctlg =9o. ec]osure --4.
6hen trind 0ll 5+at€ c"ifh fnpur lL
tefnL. +Asn s+?.
.,I D€tr.l
t^''fn of s+ctLe A'O'C"'
T draw d togrrrrn
q Ptnol SW)*' is fhct' sGPPosQ fi'na/ rs
{s then lzhe sto& uhrch cc^}tu'n qt
be4 a.tv, Fincd.
 v
1./ * mqhit, N€rDc'e W"v" I
rf. fn,6t6izalto{r lllh.
5Lept: Porl-itlon rtnoJ t ' no n 'iincrJ tfttt"
i0 b loc"L
Pr =t Jt J
bloctsE, BlocL0t

sLep 1r: rno*2 tobl'o

o I

Qo bo j tooJ
9r 1A l l t BrJ
sleP::l- )

BorJt. t -J
U r 0,'{ -J

Fz - ago/n nafee.lt LhctL TcroceJJ.

Uhex b/octS or€. corne 6o-rng Stop tt.
ProGlJo/.
tu-then Gng ,6ingle,bloct i: Arrn ,L
Foroy5 CL Sir'g/e sltrt€ ib
L{e in ftnoJ oF4

9oQt

%$a
finoJ Sto.t€ /J &JhicA tqCluele {rnal SW
.thO<rtgn r4oorug rne"ty rnephtne: @.

No F'inoj state
1> Moore:
i) Oroctt slrr,g - StGrL/crntor n I *O
2> glr.& otrrl:tr1,o +, sto*@
o
b
r- trlble
ob A
Qo Qo Q1
9
Qt QL 9t +
r l4eoJgr)Orocu st-r/ng -Sfurb I CrnpLn I
encl
2) grw outpu*, b nput,
ol b/-$ olt
bl$ qt

t-rt.blo
dA dA
{o eo$ (r$
Qt 9r# Qr 9.
\/* Cpnv?rslon .al lloorc ma.hhnitp ., .'--.
elu[ th@tl rn-aohlrte, '

i) fo Orograrn I xate qiuen

L> Erorn dt%fr te-b le.

st€P L: ra-rDove tg u olP + Put iL ,n tp
5&.e
o I

9t 9rlo q)-l o o refn ore- I SI :z

qo - znd
Qr I rlo l,
Q,t Qrlo qol I

lxha^ cq I olP O.je- lQ,\o-ve

drcru.r diugr6q6

CI
 - {D 'Dtqe7l,,rnt
\,4 ^,rlOgte
F+eo+$ rnoohrm TB8EJY
@.
tad-- 6 o.n p
?\^L ql hcrs olP.o.
C
o o p
.\
Qr
Qr 9r 9z- o q5 I
9z Qr Qs o
Qo Qr q3 I

$ doah the ull olP '

..') l0ec*lg rarut htfie rr) moDle fitst druuj

dtogrcrrn rt t"tot,
- givenf+roro
1 G.stolf,- P'
tr-rtrle)
incoP'ing Put+r ito olp
qt0P I

ru0P I I

olP cre 6cr.rne donrb SPlib

lnccmin E pubh tlo D[P

P Loq t o
f to q D I

DIP orc dff+o

q --+ 9of o
QIIJ
$ druur lqsu dlogtcrro .

+fcrq djq:."toblQ- eser,Eryr)

Iir drogro"rn Dtrt split slab al.to.
oiFPa iS irop -NFA,OFA
 oFfl
@ Conversion oF c-L
NFB 1,o
o o,b TronSiltot, l*rb\O.
-----) -\
Gb-b q
o a
drb cL
9o fooo,\ 9r
Qr 9e- + Qo

b'C- q>- 9o {eolrl Qr-

IniLluJ sb$ts = tqoj d" (qoez o)= d(qo o) ud(arcrl

dt qo cr) -- !]."01 : tqoqrJu tqot
d'C9ob) =tqrJ : I goQrJ
o d'r9o c) : @
d(qoq' b) = dC qo o)0(9r b)
=
9rUQS9r
dCqo q) u d( ao h) = {qoq,9t !-
diqoq r Q) = d(eo9,- c) = d(qo c) u d(qo- c)
= goQr U Qr .= .0Uq:-
@.
= Qo9
***
rQz @. rJ LI h)

6'(9os, b). dCqo b) u f'(aor

b)
-- Qr U0 t
b
brC q
d'(qoqr O = d(90 c)u Jtar e) o
0uqo I 9z
= Qo.

o)ucf(qq b) u c[qq9 *
Jcqoq,q,- q) = d[Qo b.1 d rour,ng
= tqoq 'J utuj utfroJ drcw ando
= 9o9t9z of glve,n

b) = CCqo b) uJ(q r o) u d(q"

I
b)
dtqoq ,q' d/og rcuo
: 9rU e g clo9a o,s0.

9oQr9:-
6'[qo9r Qr t) = d(9o Ou dCQrc)ud( 9r c)
= + U9ou9r
= 9o9t
 I (.:t bob=brba b ;
.bbebo t,ueboeb<brbob
) =

(o -bbtn=b'bqb)fr =
(rr a ) p soD ) = ( o er )I
-
"<=6._rib
(tun = ==
l.'::l;i.
(On-buo 6n ob)-P)arnsoo: =
(q a:[ir[,r bb'b )p ) arn5op 3"
(q u )-P )arnsoltr 3 -'(q v),P
ffiu:
.-Iob t-) o (sb} ltstl Drosorr a :.

(to ebrb'6ob)p)lrnsot: ? =
(to U)p)'Snsor: e- (o U),-p
i))

V. ebt b tbob =
(o b) 'arn soltr
? = dro?9 tDnlul
o
[rbeb ] ' (+6J to amp;> 3
teb ) = (qoJ 10 a.ro(bD 9
[-b ] = Go: Jo o-msob
\ o5zi6 r6 ], =' (,olo arr)sop =?
feb'zb',1job I (ob) lo a.rnse/) ?
q
?
g
_J

3
.YJ6 Oq? UJN ?
 19 9ao
q q

? -O

d
(q sbeb )arnror) a (ao)p
boab
Conlo) = (o @)P

\/
Cc +beb-ob )amrsr> ? = (9 ) )"P
' o--+bab
Canibnb) -(-
(p + 6c5-c6 ) a.nl$op ? --(o ) ),P
bz-=
) b a6zb
(On0n-lrbn0n=bJ ._t- !'

(q bbqs?.b rbab ) o-rnsop ? '(q et)P

 4 . [g J),
6=(o alp
3 _-(q
A)p
@ = (P a)-P
0 . (q r ) p
?:(o) )p
O--eb
b ' (q o )p
G=vb)=cos)P
st+Fu
(+I n@-Fa =
G,b) (e ob)P )rnrpD ) =
q O
E_........_-----.- G q) p) soo r =(q U,lg
-g= (sbebabl
a q
__

(=b) $c|e a :
t, (-b n 6 )mf. e -
(o,bo(o ob)_p)sottrD =

((D U)-p)sor. ? = Co U).p

V. I tbob] :ob orTD1g fo!1lut
{r!t _ (tu)
I
r.tbt Ou1
(sb)=(.rj
I 1r tJ.-/ (-sae,
bbbi = toi i
t [-s6'ab] I = G.61
(jieotb? - (-b)
l'b%) : (t53
f,bo bI =(obl sop?
q

@ q ? e <_ '9 €
D ? .D
 Fatbeb l = (qtq)
:
[-,b, ob t tg oO

f(q) sb ['a] -sb b

t'dt eb {'0leb +b
-sb s6 eb
Ita I {ts}
{ta1 eb s8 l ob lb
sQl tb ot
{tett s6 I
-r)
g
'zQ rQ oO
ffir'+? f sb +b eb ) f rboblr =ad

^'5.b+bebl [r o'o ]
[ob]' (oo L
f tb. abl= ['o oo ]
I
rg sb rg sb s6
I tQl 'e6 tQ) €.b 'bb
I Iq s6 ,Q/ S6
I eb
q61, q og nb o zS
-v (€, ob -rb
'<g LO )
eb o0
-
"9 rQ sb o0 rb ob
t 6? [r6tr6eb1 l, bsbl = q, ,
q D
t
uo nllto{ 'lr'ou"oI
t+ b'X;b'obI, td
etg l':au.ra -uot, g fpulJ uot1t1lt)4
9 ro
g'o q
g
q,D p

p
luow?JiuJ.ruthJ @
 ?rq
c
a n,? ,p
q
D 1)

tlJe laut6.uo so dLtrDs :-( e;ra>1s

uf'olQ.' ! UJ UJ ot41 d)wH
{-h b)[ab] ["0] {", bt f"b 1
' e6
= fog oAo& 1
ob= [oqoOtO] ry
foq\eb tq]tb {os eb 1
eb
ab f [q I tl) ob
r oql eb |os)
o g' o
r i.%i I ,'81 reT ob'l 3d
ruBo
'fob]={- to t0 09?
{ abt fott 'e '0 t
(r ra) . f ,Q'A 'Q t
f sA, obJ= ['oQc0,s]
rg oQ
[15b.b'bt [ebob'[ -,d
rEt,u-uou $ rouu uolltlrDd
tg nb (q $b osleg -bb
^
ag eb cg €b foOl cb eb
a0 eb tg -ub (g rb -b -^
LCI +b rorb
tg rlo rb,.
ag eb og eb rg tb ob

c q o
.W g
/-ltz6'5 l'ob) D,q'o? fig e5z.6rb obt
 6
'' 1b o -7b ab
c ob z-l
t 'C6 o
t6
o '[6 o 2-b

o ,tb o t"b ob

q D a,qt4
o/o
o z)

o/q ofP
o/q a ,^.
.\ q :aV.t V)a[*l Ft-aW

'["bl=ob
V(. €'v
T r$ 'Lb qb
o eb ab -cI 6<- 3x € . _p
0 t$ -$ tb fT'o1 =p
o tb g ob ob [q 'D] -?
aA
q t? I s,, -b ,b ob ]=g j s"ldnI
Y
"r()
}J

g
q
q n
.'aL/.rqcouJ arooh
-O
p
<$q q q)q eb G---=-----:-
q u g
gi! v q-Qq q fl
q
Ud 1c atdcul9
o rno
qDg Ptra I tI dto saat6 aurqrou [fou* J arooqJ g

1ovlrQb lsJ frfuuW .Pll+.euo)@

\
r
O. Moore l- rner{y. binory inPub *qn' Su-b55r1113 o,o
olP H 4 ttO efien x o-@ $

o o 6"r
@
1

I
I

I a
o

O ?\

A @nversion OF ff)ootp f-o rneoJY.'

o I I @ or A

P 5 p o P 5 Plo
qr q q ll
q i
q I

r
I
I r 5 o Y rlo 5
5
I
I 6 p o b 5 PJo o

@ o I @ o A
P s Plo p 5/o PIo
q q r I g qtfi tlo f
f r 5 o r rls 5io
S S Plo o 5 SJo P)
\ lo
D
I
l oJl
@ P/o
P 5
'r !' qI1 r t o tlo
o l o
r r 5 rt$.
S 5 Plo o oI D
 a. (o+:. 66y )*)* t'

o-r- l Cot) F)

o+ ( ol)x)x
'l

e
e o )e
€

o
9- e

e
t (ot)h e

I C Cot

e
€ o1 b

e.

/
0 aCo+b)*b + bC a+b)ho

o +b)x

_l
e o-l b €
I

{
I

e CI+ b)ts

\1
4?
{ \
<.
\
\
a e co+ b € b

€
e e+b e

/g \
L a e
b
e €

b bco+b) € a
.,
e
J---l a+b €
7

e cL .<.,

"\
 O. Co+oD'a abbr-

+ b) x abut
@
Ca+ € CL € b r
e
.7 €
e e G
---)

e
e €L
€

e h
---J
 sAtFRoN
A l-
5 Push Ocxrn Rutornu+,s DATE
FAGE ITC

fl Po n ig oo{hl btl*, Ti ni@ C,-u.trrnqt(r (^Jith

q,la, is {'orru'rqtr d rO 0 fottourin
m
(l.lhorB.
Q lser of g+oip,
E - sei- o€ in ut, oJ PhclbaJa
r- '.o}oa-Kclphctba-t
Qo I I(-ttHOl 6t(iba,
7 c-.' SLorU 6grDbo\ C ForHcl}le$ sKre}< sqfnb\).
f .Gn 3\,edsi-
Qx(fulo XY->O I^-

r,-z T.O \ 0Rf\ P

AE, 15 delino
q5 lnn o:ntrgurollon ol PoF cr.u'
I

.' t't.t I- ) whqrq

q ,. sta-l,e-
Ul 0.L -ki
F . 510.L Cd\ic\ifrt-
ru Pol oF POfl,
(D Glalsr.nio't5Hc, P str ( o PgB)
[..bn- da_lerTsr i n ish^ c N s)

Oiog rcrmmollc hep faJenLo.Eroo ctr POA

CcaP FgQat
Co u ol ,

{rnr'!e conld
 N SAFFRON
PAGE NO.

DATE;

a) Saline CFG.
R ele t>lructlrfg oI lofn{^nar ts clqftned b
+ lss denotPd oS G \r rJg P,5) urharo
Y, tinibe sa*. o{ non- hP-i rorrW iteLl YTJ.J]GbIq)
-t:Selo I tp-rcotncu Csrurcrtt ,61 1U 3 Ctl ro'b0l
P, f,inibs 3a}-of, pmdn'd,--) p L,rhare,,Q tS |+,O Sat
oc nofr- tprrnine,.l tf\g CcForbn ol )arm\tuil
\ non - tQ.rrnif\oj,
6: [u \s non-tg0nqjne! ceiltod 6tcrrL' 6 \mbo\ .

8)Oegne Nu.ll rDdn;

-T he- rDd^ R -;e ts ca}Jtesl oull rodl
9) DeEine. TuPs z ro.rnrnQr '
t> \ps hove eF mx)re res+ricJjon on bha.
Q-. qtcLmrnaJs
\eFb -ho.nd e\de- oS ecreh Ptod o fute r thot, io the
LH6 \5 o 5tn g1e- non - tetnninot nlbol
ia d---+ tr ls of f+lo fotrn
F --)
tohQfa R G\ rB \5 6Hr of
larnnrnols + non-+erat\loo]S
t_> Th\s c\usa oI qrc\rnrnors \a cqll \qel coDLqKt - Fa€,

o)Th\s
Grorsrrarers C C fc)
c-lctsscr I e $ riclr Ctods oD I ar'!S
onQrcrbpJ
U.rh'rch el.rg 6uiLo.b,le {bf rDOeIinO Co6fd1n.
al F4O 6| oC hi h - loval I Iorn(-nrt T CalO be
$Pau{:tqd q$r\ Q-cr r AfOt-eXL Fraa g re\reerar
QK: C., PflScA L.
ci>-th Of,a \}$ad in Co n) 'i\er dorr Oi
6> The. ft-creh\ n a tfleLt, O cceptx Itq e- clors of lGrtq. fs
push sD\Pn Butqgo-rqa.C pO f, ),

to) p or CfnNer:
The I ' lo.c beol b SinrLe ouioroa*€ ear\ be
dedCribe u-rt 6ar of TOd ft i5 tlr o cta
fqgulqf grOI-o\Co\OJ .
 SAFFRON
PAGE NO

C,ATE :

OFfl P.DA.
tt, i5 el fDqehlna- O:L ig rDcrahi oa
U)(l-hotr-}- nr\erno \rtf Fn rl\ef6\o Ca\€-rk

trerinc{lq gF dq'ptfra Ql3 @Gcrruro.r lq PtDA her :+

e) t-'

Ep oJ <f tue qs PoA Gra. used q5 CEL

r..xlerr lCn .o(c Hon aAC tc\b

FR i:, [oas oU"effu.l O A b nrDYe, F\d

t og f+ o.re 't (}{a-

t) DFS f> OPDft
D-) NPE ir> NPoA
s) NFtr tri Lru € '''i> PsA clccoptxd hu .mpq
q) fnesl Ll g+ct(h
==$ rnoote- i{> Doq accBptPd bU ftool

S RDtr NDOA,
l> \ess RU 1)
CFL Is t-roE Q \*d '>> N 0R CsJl hand\€,
r_-rY .T\DfD S CPL
'l=x (qJUJR
 Potrrcr oF'F+ poA q NpOA tS dtpprr
lI^uq
{ffi
SAFFRON

O.Gtfltg H.!o rn+ ds €or deftnnin I a. Ueal

b po R.
q
I h Pt QrD 6!ook.

cjqs5 o I f$n 0 teol uq opan + NPss is

Scrme . Ju+i +fue or lclso .

{dt-s

N B
n Orl \5Ara aain bo rooultl la.
SA fno\Rx urotai
tltro.ftoo. ffn NPluo is chgos C-t5
f{: ( O.'E , t- , d, 9o,zo, F)
UrbeJe. I 6eI. o{ S\c,.}s-

F I

r")+
qo " ioiuc^J
F.
-Lo
fi'nerJ
: lt'luol s\eul svrr'bol ,

n e;oss of Ctre +POft is Somq Tg E.

lrtlQ
-fhe. qlcss aT
lg g. of
R CI:'L eon ba, o zael b P.DR
- + foc E\rafU CFL +her'r Qrcts$ PoA

(r
o uJ4
 hjhlch lool io u$eaj to
TCs
longtro^g e PAGE N ;ryr
6 Begulor [o1g ucr3al ufn P inel

A $oFine toqulo.r I of\qUO 0e:

Ib i5 lJJo Lo re rasonb or tb describe o lon
Occepbed bg {roit€ quuJrrlaicL in o.Jga.bric rnc$nor,
a lcloqu0ee re PrcbenLsd bq ragu_tqr ax pto
Io ec{1pr1 qs IsgLtJo.r longu oge, {or QVQ' q raguof
lo.n qu aqs t,hair exisL CDFR.

6. Purrptin q ternmq.
La-b l'4="tO,: , C, qo , F j bo o {r n ile- qubnnaio
urruh n 5t0rc. Le| L be uha. \l{cr.I BaL g,c Q{},apl er
M LQyzeL$. lzl >, l-a tl'ren thor eK(6L Q,VrW 6UOh
thor, Z= UYLI] UiLh {uvl .-.< tzl t 1\l>o $ 0\rruleL \Si>l
lin ln.
lgrnmcr: cr-
t> Ptr-m \n lqrnrno shou.rd bo useal t0 [ovo tho.h i\ren
5 is noL ra ulojt I

2) Purn \in lerorrro ghor.rl cJ bQ. plled {a cl fobt<-rn

ins 5 CIS rYan bat

x Clo rc arL,lsB rt- UJCU tGX)

i) un ion o)Coocc*pnGtion rb) Kleene slcu
e> C:rotplementcrU oo O i0tBrseoHon,

\,-O- R u-le,-r \ : f5 closed under eaBectt€n un\on.

{v; D( ul crr 6et6 ore omaal under rro'ton , ConCgdQnatfuan
& Kleens c\osure, tt Lt $ t-z cue fog\rlor sals $harn
Lruuo ,6 t +Lq) ,Ltolrr"SLh a.re oJsD rag\!ar.

Lmion: LtuLz
inHrbQctpn:'Lr OLz
G)rnpli p6')an \uHon ++f T,
kleans s+cLr : l=t t+.
CoO CqII-en obb n Lr. [2
d ( Fperanee : Lr -Lt_
TQVQISA = LR
 Hcnbigious = leFt.ttpo * Rig hb \te,a-
N /-- saFERoN

Q. Conbe-xt Freo gra rnnna-r

PAGE NC

DATE

r> Amuiq ou6 q tocnNlQ,f :

s cgG i5 co-ltQd Or ct-rnbl ous iF lor co leersu
erp 5kr n Dfl . Lher r n\gb tor: el i
A
orsa
trpe.
v,E, P,$ be cr CE s F treqts clo.rrvufierr
>) Por6e treg: ia-E q =(
*oq frr G f F lcbol e, thQn in ib.
oR A se-L o{ cleri.bLton o.pplfeal oo Lb bhc*, co.D be.
bqnud i n hicoJ {brrn \}J hich is. ccrilqd cuot !+qB

o oQline ri hu llnerq Tcrl:nnn{J: LTUpq of tUrnmer).

H ulGr rher in Uihi.}) O non-t*r.n\noJ
I CtPol
Sqnn bol oepoeus O 6 cI f\q hb nno€iL 59 robol in epro-rr
todn Ex h --rBqlRb :

trlL line0r f Ul^hfnaj

A uJC,..f tofofnar I n urhrch o n00 - be/rDi0ctl
€) rn I ao11g Cq O, laPe rnugL f$bot
i n OarcI) rodn : E)< : ft-rer,B'l bft'

f4crcfrlnQ us€el {ot CGG Linee$ bourrded dertcr

CPG . Q.rsl, dotrrn outorDQlq

6) Oe.line CNf :

tr cFG i5 in cNf in 0nl ip rodn

ia oS
F-+ rJelO
tlnerc B C c.l\q 5H\CK n oD- tQrorn cu $ 0 i5 G}riohl
Q{forin

6) saFi ne Q$p :

Ap rodn i6 in GNE ip + Dolq iF C!-il tfp- Pm dn

OJa t $re forin
p --+ od o"
urhara A is OlricLt noD-te{-cDinau S A iG skfcr-
mi\ol g A' iS 6Hir1E O{ Oon _ terrof noJ only...