Theory of Computation 2069

Attempt all the questions.

                                                                Group A                                                         (8x4=32)

1.  What do you mean by finite automata?  Explain deterministic finite automata with example.

2.  Explain the finite automata with Epsilon Transition.

3.  Explain the closure properties of context free languages with example.

4.  Differentiate between deterministic and non-deterministic PDA.

5.  Explain the non-deterministic Turing machines with example.

6.  Define the Turing machine. What are the roles of Turing machines?

7.  What is a universal Turing machine?

8.  Differentiate between class P and class NP.

                                                                Group B                                                         (6x8=48)

9.  Design a constructive method to prove that the complement of the language accepted by an NFA is accepted by a DFA.

10.  What do you mean by regular expressions? Explain with example of pumping lemma for regular  languages.

11.  Define the non-deterministic finite automata (NFA) and write down recursive definition of for NFA.

12.  Draw Turing machine to accept palindromes over {a, b}.

13.  Give a detailed description of ambiguity in context free grammar.

14.  Explain the following:

a)      Minimization of finite state machine

b)      Push down automata (PDA).

c)      Halting problems

d)      Computational complexity