Theory of Computation PU Spring 2023 question paper

• a) Define alphabet, string, and language with examples. hs}
• b) Design a DFA for the language L = {w € (a, b)" : w ends with bb} hs}
• c) Define an ambiguous grammar. Check if below grammar is ambiguous: SaB | ab ie, ADaAB la ere) B>ABb |b

• a) What is the significance of minimizing a DFA? Minimize below DFA and analyze your finding.
• C) eC) . oe. 0 0
• b) "We can convert Finite Automata to Regular Expression and also Regular Expression to Finite Automata ". Justify this suitable with suitable examples.

• a) Can production rules realize Context Free Grammar for the language given by L={a™b" : m>0 and n>0}. How? 1
• b) Explain the process of simplifying Context Free Grammar. Simplify the following CFG, G=(V,>,R,S) Where V= {S, A} E= tab} * j \ ee ca A>aA |e B->ab | bA}

• a) Explain the concept of “epsilon transitions" ina Pushdown Automaton. How do they affect the computation?
• b) Define PDA with block diagram? Design a PDA which accepts the g language L={ a**b": n>=1 } and test for strings aaaaaabb and aaaabb.

• a) Describe the concept of an "accepting state" and a "halting state" ina Turing Machine. Show that the function, f(n) = 2n is a turing computable.
• b) Define Turing Machine. Construct a Turing machine that accepts the language of strings over (a, b) with each string of even length. Also show it accepts string abab.

• a) Define the concept of "Recursive Functions" and explain their significance in the theory of computation.
• b) Is P=NP? Explain. Also differentiate between Tractable and Intractable problems with examples.

Write short notes on: (Any two) 2x5

• a) Pumping lemma for CFL
• b) Universal Turing Machine
• c) The Halting problem 2