Theory of Computation PU Spring 2024 question paper

• a) Convert the following NFA to its equivalent DFA. 3 TASER RG ta é i EN Se Be aN Nina Des PADRE NS cog SO meclpa tN © wine Hep NE See eal i nab! ae (@) aC{ ; ) $ et
• b) Define pumping Lemma for regular language. Show that L={a" b*; n>1} is not regular using pumping lemma for regular language.

• a) What is CFG? Design CFG for language L={a"b"; m>=1, n>=1 }. Test the grammar for derivation of aaaabbb and also draw equivalent parse tree.
• b) Convert the following grammar into Chomsky Normal form. S— bAD A aB/oAB Bob D> « (Null)

• a) Define PDA with block diagram. Design a PDA which accepts the language L={a"" : n>=1} and test for strings aaaaaaaa and aaaaaa.
• b) Show that the language L= {a"b"c": n>0} is not context free using the of concept of pumping lemma. :

• a) Define Turing machine. Design a Turing machine that accepts the language L= {a"b’c" : n>=0}.
• b) How does a Turing machine compute a function of natural numbers? Describe. Show that the function f(n) = n +2 is computable.

• a) State the halting theorem and give the outline of its proof.
• b) What are P, NP and NP-Complete problems? Explain with examples. .

Write short notes on: (Any two) 2x5

• a) Simplification of CFG
• b) Recursive and Recursively Enumerable Language ¢
• c) Decision algorithm for CFL