Define NDFA and DFA with examples.

Write the statements of Myhill-Nerode theorem.

Give a regular expression in which 3 consecutive zeros appear in a substring over input 1}.

Design a Moore and Mealy machine for Binary input sequence. If it ends in output is If it ends in output is otherWise

Write down the procedure for converting an NFA into equivalent DFA.

Prove that is not equal to and r(s is equal to (rs rt).

4. Write down the statements of Kleene's theorem and also prove it.

Design a DFA for the regular expression 10 11) 0 1.

Show that n U m cannot be accepted by deterministic PDA.

6. Design a Turing Machine that accepts

0^N 1^N N 1}.

7. Design a Moore and Mealy machine which prints the one's complement of the binary number 0011.

8. Explain recursive and recursively enumerable language with its application and also compare and contrast decidability and undecidability.

9. What do you mean by an unsolvable problem Explain.

10. Write short notes on any two of the following:

GNF

Pumping Lemma for Regular Sets

Travelling Salesman Problem