2006 Anna University B.E CSE THEORY OF COMPUTATION Question paper

[ganeshbala]

2006 Anna University B.E CSE THEORY OF COMPUTATION Question paper

ANNA UNIVERSITY :: CHENNAI – 600 025

FIFTH SEMESTER

B.E. COMPUTER SCIENCE AND ENGINEERING

CS332 - 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={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 )