B.E.—COMPUTER SCIENCE & ENGINEERING—IV SEMESTER
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
1
2
1
2
2
0
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
iCtS iCtSeS a C
b
→
→
/
/ ,
(a) Generate a sentence ‘ibtibtaea’ using leftmost derivation and construct a derivation tree for it.
(b) Derive an equivalent chomsky normal 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.
(b) Construct a Turing Machine that will accept the following languages
in {a, b}
L a b n
n m
n m
=
≥
≠
{
,
,
}.
1
25. (a) Explain the basic properties of linear cellular Automata.
(b) Draw any 3 common types of Cayley graph.
University Question Papers
337