MORE IN Theory of Computation
SPPU Information Technology (Semester 5)
Theory of Computation
May 2017
Total marks: --
Total time: --
INSTRUCTIONS
(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 from Q.1(a,b) &Q.2(a,b)
1(a) Construct FA that accepts even number of zeros & odd number of ones.
6 M
1(b) Write formal definition of regular expression with suitable example. State Arden's theorem and its use.
4 M

2(a) Construct a Moore machine to find out the residue-modulo-3 for binary number.
6 M
2(b) Define regular sets. List out closure properties of regular sets.
4 M

Solve any one question from Q.3(a,b) &Q.4(a,b)
3(a) Define the following and give apporpriate examples
i) Derivation tree
ii) Context free grammar.
6 M
3(b) Conevert right linear grammar to its equivalent left linear grammar.
S→bB
B→bC
B→aB
B→ b
C→a
6 M

4(a) Construct a DFA equivalent to the following grammar
S→S10|0
6 M
4(b) Write a short note on the applicaitons of CFG.
4 M

Solve any one question from Q.5(a,b) &Q.6(a,b)
5(a) Design a PDA that checks wellformedness of parentheses. Simulate PDA for (( ) (( )) ).
8 M
5(b) Define and compare DPDA and NPDA. Justify that NPDA is more powerful than DPDA.
8 M

6(a) Construct a PDA for the language generated by the following grammar.
S→aB|bA
A→bAA | a | aS
B→b |bS| aBB
8 M
6(b) Define post machine. Compare FA, PDA and post machines.
8 M

Solve any one question from Q.7(a,b) & Q.8(a,b)
7(a) Write a short note on:
i) Church Turing Hypothesis
ii) Post correspondence problem.
8 M
7(b) Design a Turing Machine to recognize the language $$L = \left \{ 1^{n} 2^{n}3^{n}|n> =1\right \}.$$/ Simulate TM for "112233".
10 M

8(a) Design a Turing machine that accepts $$L = \left \{ 0^{n} 1^{n}|n< =1\right \}.$$/ Simulate TM for "00011".
10 M
8(b) Explain the following for a TM
i) Power of TM over finite state machine
ii) Universal TM
8 M

Solve any one question from Q.9(a,b) & Q.10(a,b)
9(a) Write a short note on decidable problems concerning
i) Context free languages
ii) Turing machines
8 M
9(b) What is reducibility? What are undecidable problems? Describe at least four undecidable problems in case of CFGs.
8 M

10(a) Describe post correspondence problem. PCP is an unsolvable problem. Justify.
8 M
10(b) What are recursive and recursively enumerable languages? What is the relation between them?
8 M

More question papers from Theory of Computation