B.E. COMPUTER SCIENCE AND ENGINEERING
CS332 - THEORY OF COMPUTATION
------------------------------------------------------------------------------------------------------------
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.
------------------------------------------------------------------------------------------------------------
b) Prove that a balanced parenthesis is not a regular language. (8)
b) Show that L = {an! : n>=0} is not regular. (8)
b) Convert the grammar S->ABb|a, A->aaA|B, B->bAb into greibach normal form. (8)
(OR)
(b) Prove that {op | p is prime} is not context free. (8)
b) Prove the equivalence of two-way infinite tape with standard Turing machine. (8)
b) Prove that halting problem is undecidable. (8)
b) Prove that there exists an recursively enumerable language whose complement is not recursively enumerable. (8)
No comments:
Post a Comment