Theory of Computation 2068

Attempt all the questions.

                                                                Group A                                                         (8x4=32)

1.  Define finite automata. Give the formal definition of deterministic finite automata with example.

2.  Give the DFA for language of strings over{a,b} where no two consecutive a’s occurred.

3.  Show that language of palindrome over {a,b} is not a regular language.

4.  What do you mean by a CNF grammar? Convert following grammar in CNF.

S → AC|ɛ, A → aS|a, C → BC|aC|b.

5.  Define Deterministic Push Down Automata. How it differs with a Finite Automata.

6.  Give formal definition of Turing Machine. Explain the roles of Turing Machine.

7.  Construct a Turing machine that accepts the language of palindrome over {a,b}* with each strings of even length.

8.  What is universal language? Explain.

                                                                Group B                                                         (6x8=48)

9.  Show that for any regular expression, there is a NFA that accepts the same language represented by r. Convert the regular expression (a+b) (aa+ba)* + ab(a+b)* bba into NFA.

10.  How a NFA can be converted into a DFA? Convert the following NFA into equivalent DFA.

11.  Define CFG. Convert the following CFG into Chomsky Normal Form.

S → |Sbb|aabb|Aa|Bb,

A → Aa|a,

B → Bb|b|ɛ

12.  Define the language of PDA that accepts by Final state. Explain, how a PDA accepting by empty stack can be converted into a PDA final state.

13.  Explain about multi tape TM. Show that every language accepted by a multi-tape Turing Machine is also accepted by one tape Turing Machine.

14.  Explain the following terms.

(a)  Big Oh and Big Omega

(b) Class P and NP

(c)  CNF SAT Problem

(d)
Turing Decidable and Acceptable problems.