Theory of Computation 2070

Attempt all the questions.

                                                                Group A                                                         (8x4=32)

1.  Differentiate between deterministic and non-deterministic finite automata.

2.  What do you mean by pumping lemma for regular languages?

3.  Explain the non-deterministic PDA with example.

4.  Define Turing Machines.  Draw NFA - ε corresponding to following regular expression over  ∑ = {0,1} 

                    010* + 0(01+10)* 11

5.  Explain about recursive enumerable and recursive language.

6.  Explain the computational complexity with example.

7.  Differentiate between class P and class NP.

8.  Compare FA, NFA and NFA- ε with illustration.

                                                                Group B                                                         (6x8=48)

9.  Define finite automata and draw FA for the strings.

10.  For the following regular expression draw an ε- NFA  recognizing the corresponding languages.

                           i. (00 +1)*(10)*

                           ii. 001*0*11

11.  Define CFG. Prove the following CFG is ambiguous.

S→S+S | S*S | (S) | a

Write the unambiguous CFG for the above grammar.

12.  Draw Turing Machine (TM) to accept  palindromes over {a, b}. (Even as well as odd Palindromes).

13.  Prove that any regular language can be accepted by a finite automata with all details.

14.  Explain the following:

a)      Regular Grammar

b)      Halting problem

c)      Chomsky hierarchy

d)      NP-complete Problem