STUPIDSID
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.
!mage.
!mage.
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.
S->AA|0
A->SS|1
S->AA|0
A->SS|1
6 M
Solve any one question fromQ.3(a,b) and Q.4(a,b)
3(b)
Consider CFG with productions
S->baXaS|ab
X->Xab|aa
If w= baaaaabababaab then give rigtmost derivation and leftmost derivation of w.
S->baXaS|ab
X->Xab|aa
If w= baaaaabababaab then give rigtmost derivation and leftmost derivation of w.
4 M
4(a)
Convert the following grammar to their equivalent CNF.
S-1A|0B
A->1AA|0S|0
B->0BB|1S|1
S-1A|0B
A->1AA|0S|0
B->0BB|1S|1
6 M
4(b)
Convert Left Linear Grammar to equivalent Right linear Grammar.
S->C0|A0|B1
A->A1|C0|B1|0
B->B1|1
C->A0
S->C0|A0|B1
A->A1|C0|B1|0
B->B1|1
C->A0
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
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.
S>0A1|0BA
A->S01|0
B->1B|1
S>0A1|0BA
A->S01|0
B->1B|1
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 \}\]
\[\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.
i) Multitape TM
ii) Turing Reducibility.
8 M
More question papers from Theory of Computation