Theory of Computation 2076

Attempt all the questions.

                                                                Group A                                                         (8x4=32)

1.  Define DFA and explain how it differs from NFA.

2.  Define the term: alphabet, substring/Prefix/Suffix of a string with example.

3.  What do you mean by ε-closure of a state in NFA with epsilon moves. Explain with an example.

4.  Give the regular expression for the following languages over alphabet {a, b}

        a. Set of all strings ending with substring ab.

        b. Set of all strings with 2^nd and 4^th symbol is b.

5.  What do you mean by a CNF grammar? Convert following grammar into CNF.

            S→ ABa,    A→ aab,    B→ AC

6.  Construct a PDA accepting L={w | w has equal no. of a's and b's}.

7.  Describe the Turing machine. Construct a TM that accepts even length strings from alphabet {0, 1}.

8.  What do you mean by Intractability? Explain in brief.

                                                               Group B                                                         (6x8=48)

9.  Explain about sub-set construction method to convert a NFA into equivalent DFA with suitable example.

10.  State and prove the pumping lemma for regular language. Explain about its application.

11.  Explain about the closure properties of regular languages. Show that for any regular languages L₁ and L₂, L₁∪L₂ is also regualr.

12.  What is a regular grammar? Explain with example, about the method of converting a regular grammar into equivalent Finite Automata.

13.  Define PDA. Explain how a PDA accepting by empty stack is converted into equivalent PDA accepting same language by final state.

14.  What is Universal Turing machine? Explain about the working mechanism of Universal Turing machine for processing the binary code input for (T, w) where T is specific Turing machine and w is input to T.