THEORY OF COMPUTATION 2006 - B.E CSE

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={anbn|/n>=1}U{amb2m/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 = {an! : 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)={aib2i/I>0} and L(G2)={anban/n>0} (8)

(b) Prove that {op | 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)