Theory of Computation 2073

Attempt all the questions.

                                                                Group A                                                         (8x4=32)

1.  What is finite automata? Define DFA  with suitable example.

2.  Differentiate DFA with NFA. Design an NFA  accepting strings over {0, 1} that end in 01.

3.  Give formal notation for an ε-NFA with example.

4.  Write regular expression for the set of strings of 0's and 1's with at most one pair of consecutive 1's.

5.  What is CFG? Design CFG for palindromes with alphabets {0, 1}.

6.  What is PDA? How is it different from finite automata?

7.  Design a Turing machine that accepts the language {0ⁿ1ⁿ|n≥1} over {0, 1}.

8.  What is recursive language? Explain.

                                                                Group B                                                         (6x8=48)

9.  Convert the following NFA into equivalent DFA.

10.  How do you convert a regular expression to automata? Convert the regular expression (0+1)*1(0+1) to auatomata.

11.  Convert the following DFA into minimum-state equivalent DFA.

12.  Convert the following CFG into CNF.

13.  Discuss the equivalent of PDA and CFG. Convert the grammar

           S→aAA

           A→aS|bS|a

        to a PDA that accepts the same language by empty stack.

14.  Write short notes on:

        a) Turing maching

        b) Classes P and NP