SPPU Information Technology (Semester 5)
Theory of Computation
May 2017
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 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.
B→ b
6 M

4(a) Construct a DFA equivalent to the following grammar
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.
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