# Anna University V Semester B E CSE theory Of Computation

**ANNA UNIVERSITY V Semester B.E. CSE**

**THEORY OF COMPUTATION**

**TIME: THREE HOURS**

** ****MAXIMUM : 100 MARKS**

**ANSWER ALL QUESTIONS**

**PART A – (10 X 2 = 20 MARKS)**

1. What is the difference between DFA and NFA?

2. Give regular set for the following expression: 1(01)*(10)*1

3. For the grammar G defined by S->AB, D->a,A->Aa,A->bB,B->Sb, give derivation tree for the sentential form babab

4. Give pumping lemma to prove that given language L is not context free.

5. Give formal definition of PDA.

6. Give an example of a language accepted by a PDA but not by DPDA.

7. Prove that the function f(n)=n-1 is computable.

8. Design a Turning machine to compute n mod 2.

9. What is undecidability?

10. Differentiate between recursive and recursively enumerable language.

** **

**PART B – (5 x 16 = 80 MARKS)**

11. Construct a context free grammar for the given language L={a^{n}b^{n|}/n>=1}U{a^{m}b^{2m}/m>=1} and hence a PDA accepting L by empty stack (16)

12.a) Prove the equivalence of NFA and DFA. (8)

b) Prove that a balanced parenthesis is not a regular language. (8)

**(OR)**

12.a) Explain in detail with an example the conversion of NDFA to DFA (8)

b) Show that L = {a^{n! }: n>=0} is not regular. (8)

13.a) Explain in detail the ambiguity in context free grammar. (8)

b) Convert the grammar S->ABb|a, A->aaA|B, B->bAb into greibach normal form. (8)

**(OR)**

13.a) Construct a context free grammar for the languages L(G1)={a^{i}b^{2i}/I>0} and L(G2)={a^{n}ba^{n}/n>0} (8)

(b) Prove that {o^{p }| p is prime} is not context free. (8)

14. Construct a Turing Machine to do the proper subtraction (16)

** (OR)**

** **

14.a) Construct a Turning machine to perform multiplication (8)

b) Prove the equivalence of two-way infinite tape with standard Turing machine. (8)

15.a) Discuss in detail about universal Turing machine. (8)

b) Prove that halting problem is undecidable. (8)

**(OR)**** **

15.a) Prove that the union and intersection of two recursive languages are also recursive. (8)

b) Prove that there exists an recursively enumerable language whose complement is not recursively enumerable. (8)

## Recent Comments