1.a. Explain Chomsky Hierarchy.

1.b. Differentiate 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 has no substring 00

1.d. Explain Halting Problem.

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

2.b. Give the definiton of Pumping Lemma for regular language and prove that following language is not regular .

$\mathrm{L}=\left\{\mathrm{a}^{\mathrm{m}} \mathrm{b}^{\mathrm{m}-1} | \mathrm{m}\gt0\right\}$

3.a. Construct PDA accepting the language $\mathrm{L}=\left\{\mathrm{a}^{2 \mathrm{n}} \mathrm{b}^{\mathrm{n}} | \mathrm{n} \geq 0\right\}$

3.b. Consider the following grammar

$\mathrm{S} \rightarrow \mathrm{iCtS} | \mathrm{iCtS}$ e S|a

$\mathrm{C} \rightarrow \mathrm{b}$

for the string 'ibtacibta' find the following :

i) Leftmost derivation

ii)Rightmost derivation

iii)Parse tree

iv)Clock if above grammar is ambiguous.

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

4.b. Convert following CFG and CNF

$\mathrm{S} \rightarrow \mathrm{ASA} | \mathrm{aB}$

$\mathrm{A} \rightarrow \mathrm{B} | \mathrm{S}$

$\mathrm{B} \rightarrow \mathrm{b} | \in$

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:

6.a. Closure properties of context free language

6.b. Applications of regular expression and finite automata

6.c. Rice's Theorem.

6.d. Moore and Mealy Machine.

6.e. Universal Turing Machine.