Theory of Computation 2071

Attempt all the questions.

                                                                Group A                                                         (8x4=32)

1.  Explain the extended transition function of NFA.

2.  Construct a DFA that accepts all the strings of alphabet {a, b} having each strings with even number of 0’s and even number of 1’s.

3.  How can you convert an ɛ-NFA into equivalent DFA? Explain.

4.  What are the regular operators applied to the regular languages? Explain with example.

5.  Simplify the following regular expressions.

a.) 1*+1*0(ɛ+0+1)*ø

b.) ɛ+0+1+( ɛ+0+1)( ɛ+0+1)*( ɛ+0+1)

6.  what do you mean by a CNF grammar? Convert the following grammar into CNF.

                    S→abSb | aa

7.  what are unrestricted grammar? How they differ with CFG? Explain.

8.  Define the term Class P and Class NP with example.

                                                                Group B                                                         (6x8=48)

9.  What are the algebraic rules for regular expressions? Also show that if L, M, N are any regular language then show that L(M U N) = L.M U L.N.

10.  Prove that for any given NFA N accepting a language L there exists a DFA D such that L(N) = L(D). 

11.  Define regular grammar. Show with suitable example that the language described by regular grammar are accepted by a finite automata.

12.  What do you mean by the Chomsky Hierarchy in the formal language theory? Explain in detail. 

13.  Construct a PDA that accepts a language of palindrome of even length from an alphabet {a,b}.

14.  Show that a Turing Machine with one tape and a Turing Machine with multiple tape are equivalent.