Construct a minimum state automaton equivalent to the following DFA <img src='./qimages/13489-1a.jpg'> Design a DFA accepting all strings over ending in ab.

2.(a) Construct a DFA accepting all strings over where number of is divisible by 3 and is divisible by 2.
Construct a Mealy Machine which can output even, odd according to the total number of even or odd encountered. The input symbols are 0 and 1.

3.(a) Define grammar and describe the Chomsky hierarchy of grammar.
If G 0Sl, S find

4.(a) Construct a regular expression corresponding to the state diagram described by

<br><br> <img src='./qimages/13489-4a.jpg'> Show that L 1i is not regular.

5.(a) Find the regular expression representing the set of all strings of the form

a^m b^2n where p 1.
Find a regular expression corresponding to each of the following subset The set of all strings containing exactly two a's.

(ii) The set of all strings containing the substring "aa".

6.(a) Convert the grammar S AB, A BS|b B SA|a into GNF.
Define Decision algorithm for context free language.

7.(a) Convert the grammar S aSb A bSa A to a PDA that accepts the same language by empty stack.
Construct a PDA accepting by empty store for the language L b^2n 1}.

8.(a) Define the CYK algorithm.
Define the Turing Machine Model.

9.(a) Design a Turing Machine for the language L c
Define recursive enumerable language.

10. Attempt any two from the following: Define undecidable languages. What is the description of a finite automata? Define the procedure for transforming a Mealy Machine into a Moore Machine.