22. Construct NFA for the following regular expressions. Show the
sequence of moves made by the each in processing the input string
“ababbab”.
(a) (ab)* (ac)*
(b) (a / b)* abb (a / b)*
(c) (a* / b*)
23. Construct GNF for the BNF grammar S
AB A B B
aB Bb
→
→
→
,
,
| | .
ε
24. Construct Turing Machine for identifying the language consisting of 0’s
and 1’s in which all the string consisting of even number of 0’s and odd
number of 1’s.
25. The roles played by Linear Cellular Automatadiscuss. Explain Global
maps and dynamical systems.
THEORY OF COMPUTING
Time: 3 Hours
Max. Marks: 60
GROUP III
21. Let M
q q q
q
q
= ({ , , }, { , }, , { }, { })
1
2
3
1
3
01 δ
is a NDFA where δ is given by
δ
δ
δ
δ
( , ) { , } ( , ) { }
( , ) { , } ( , )
q
q q
q
q
q
q q
q
1
2
3
1
2
1
2
2
0
1
1
0
1
=
=
=
= { }
, ) { }
( , ) { , }
φ
δ(
δ
q
q
q
q q
3
2
3
1
2
0
1
=
=
(a) Construct an equivalent DFA and draw the transition diagram.
(b) Check whether the string ‘011010’ is accepted by DFA and NFA.
22. Consider the grammar with the following productions
S
iC t S iCtSeS a C
b
→
→
/
/ ,
(a) Generate a sentence ‘ibtibtaea’ using leftmost derivation and construct a derivation tree for it.
(b) Derive an equivalent chomsky norma form productions.
23. (a) Construct a PDA for the given grammar
S
AaA CA BaB
A aaBa CDA aa DC
B
bB bAB bbaS
C Ca bC D
→
→
→
→
/
/
/
/
/
/
/
/
/
D bD
→
/ .
ε
(b) Using the above show the sequence of PDA for the string
‘aabbaaaaaaa’.
24. (a) State the problems in Turing Machine.
328
Theory of Automata, Formal Languages and Computation