SPPU Information Technology (Semester 5)
Theory of Computation
December 2016
Total marks: --
Total time: --
(1) Assume appropriate data and state your reasons
(2) Marks are given to the right of every question
(3) Draw neat diagrams wherever necessary

Solve any one question fromQ.1(a,b) and Q.2(a,b)
1(a) Construct a deterministic finite automata (DFA) for accepting Lover (0.1) such that every sustring of length 4 contains at least three 1'S.
4 M
1(b) Construct DFA for the R.E 10+(0+11)
6 M

2(a) Construct Moore machine for given Melay machine.
6 M
2(b) State the pumping lemma theorem for regular sets. Show that the language L{00| n is prime} is not regular.
4 M

3(a) Conevert given CFG to GNF.
6 M
Solve any one question fromQ.3(a,b) and Q.4(a,b)
3(b) Consider CFG with productions
If w= baaaaabababaab then give rigtmost derivation and leftmost derivation of w.
4 M

4(a) Convert the following grammar to their equivalent CNF.
6 M
4(b) Convert Left Linear Grammar to equivalent Right linear Grammar.
4 M

Solve any one question fromQ.5(a,b,c) and Q.6(a, b,c)
5(a) Define PDA
i) Through final state
ii) Through empty stack
4 M
5(b) Design a PDA for the laguage L={an bm cn| m, n>=1} by empty stack.
8 M
5(c) Construct PDA equivalent to the following CFG.
6 M

6(a) Give CFG generating the language accepted by following PDA \( M=\left ( \left \{ q0,q1 \right \},\left \{ a, b \right \}, \right\left\left \{ z0, X \right \}, \delta , q0,z0\phi}),\delta \)/ is given below
\[\delta \left ( q0,b,z0 \right )=\left \{ \left ( q0,Xz0 \right ) \right \}\\\delta \left ( q0,b,X \right )=\left \{ \left ( q0,XX \right ) \right \}\\ \delta \left ( q0,a,X \right )=\left \{ \left ( q1,X \right ) \right \} \\\delta \left ( q0,\varepsilon ,z0 \right )=\left \{ \left ( q0,\varepsilon \right ) \right \}\\\delta \left ( q1,b,X \right )=\left \{ \left ( q1,\varepsilon \right ) \right \}\\ \delta \left ( q1,a,z0 \right )=\left \{ \left ( q0,z0 \right ) \right \}\]
8 M
6(b) Design PM to for L={an bn cn|n>=0} Can you design NPDA for same? Justify.
6 M
6(c) Compare the power of Post machine and Push down Automata.
4 M

Solve any one question fromQ.7(a,b,c) and Q.8(a,b)
7(a) Design a Turing Machine to add two unary numbers.
8 M
7(b) Explain Halting problem of TM.
4 M
7(c) Differentiate between FA, PDA and TM.
4 M

8(a) Construct TM to replace string 110 by 101 in binary input string.
8 M
8(b) Write short note on Universal Turning machine.
8 M

Solve any one question fromQ.9(a,b) and Q.10(a,b)
9(a) Explain Post Correspondence Problem with example.
8 M
9(b) Explain recursive language and recursively enmerable language with suitable example.
8 M

10(a) Define decidability of problem with example. Describe undecidable problems for Context Free Grammar.
8 M
10(b) Write short note on
i) Multitape TM
ii) Turing Reducibility.
8 M

More question papers from Theory of Computation