1.a. Explain Chomsky Hierarchy.

1.b. Difference between PDA and NPDA.

1.c. Define regular expression and give regular expression for

i) Set of all strings over {0,1} that end with 1 and has no substring 00

1.d. Explain Halting Problem

2.a. Define the finite state machine to determine the ternary number (base 3) is divisible 5.

2.b. Give and explain formal definition of Pumping Lemma for Regular Language and prove that the following language is not regular

3.a. Construct PDA accepting the language

3.b. Consider the following grammar

for the string 'ibtaeibta' find the following :

(i) Leftmost Derivation

(ii)Rightmost derivation

(iii)Parse tree

(iv)Check if above grammar is ambiguous.

4.a. Construct TM to check wellformness of parenthesis.

4.b. Convert following CFG and CNF

5.a. Convert (0+1)(10)*(0+1) into NFA with $\epsilon$-moves and obtain DFA.

5.b. Construct Moore and Mealy machine to convert each occurence of 100 by 101.

6 Write short note on any four -

(a)Closure properties of Context Free Language

(b)Applications of Regular expression and Finite automata.

(c)Rice's Theorem

(d)Moore and Mealy Machine.

(e)Universal Turing Machine