CS332 - THEORY OF COMPUTATION

[aruljothi]

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.                   (
     b)   Prove that a balanced parenthesis is not a regular language.                (

(OR)

12.a)   Explain in detail with an example the conversion of NDFA to DFA                   (
     b)   Show that L = {an! : n>=0} is not regular.                            (

13.a)   Explain in detail the ambiguity in context free grammar.                      (
     b)   Convert the grammar S->ABb|a, A->aaA|B, B->bAb into greibach normal form.                                              (
(OR)

13.a)   Construct a context free grammar for the languages L(G1)={aib2i/I>0} and L(G2)={anban/n>0}                            (
(b) Prove that {op | p is prime} is not context free.                (

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

     (OR)

14.a)   Construct a Turning machine to perform multiplication            (
    b)   Prove the equivalence of two-way infinite tape with standard Turing machine.                                                       (

15.a)   Discuss in detail about universal Turing machine.                         (
     b)   Prove that halting problem is undecidable.                            (

(OR)

15.a)   Prove that the union and intersection of two recursive languages are also recursive.                              (
b)   Prove that there exists an recursively enumerable language whose complement is not recursively enumerable.                               (

-----