Theory of Computation

b) Briefly explain Cook's Theorem.

a) Briefly explain Chomsky classification of languages, with examples.

b) Draw a DFA for all strings over {0,1} consisting or even no or U'S and even no of l's. 

a) State and prove Pumping Lemma for Regular Languages. Also prove that language L= {aⁿbⁿ  for n=0,1,2,3......) is not regular. 

b) What is PDA? Construct a PDA accepting the set of all strings over {a,b} with equal no. of a's and b's.

a) What are the different closure properties of CFL? Explain with proof. 

b) State Pumping lemma for CFL. Provide an example to understand.

a) State & explain Halting Problem.

b) What is Turning Machine? What are it's different variant? Explain. 

a) State and prove Savitch's Theorem.

e) Differentiate between Moore Machine and Mealy Machine

Write short note on:

a) Space & Time Complexity

Write short note on:

b) Turing Church's Thesis 

Write short note on:

c) Chomsky Normal form

b) Find a Reo Find a Regular Expression corresponding to each of the following subset (0,1): 

i) The language of all strings containing atleast two O's.

b) Find a Reo Find a Regular Expression corresponding to each of the following subset (0,1): 

ii) The language of all strings Containing atmost two U's

a) Consider the CFG whose Productions are 

i) Left Most Derivation 

a) Consider the CFG whose Productions are 

ii) Right Most Derivation 

a) Consider the CFG whose Productions are 

iii) Parse Tree

a) Differentiate between DFA and NFA.

b) What is Ambiguity? How it is removed?

c) Define Recursively Enumerable Language. What are its Different Properties?

d) Differentiate between NP-Hard and NP-Compare Problem.