1.a.i. Define the following with example : String

1.a.ii. Language

1.a.iii. Alphabet

1.a.iv. DFSM

1.b.i. $\mathrm{L}=\left\{\mathrm{W} \in\{0,1\}^{*} : \mathrm{W} \text { has } 001 \text { as a substring }\right\}$

1.b.ii. $\mathrm{L}=\left\{\mathrm{W} \in\{\mathrm{a}, \mathrm{b}\}^{*} : \mathrm{W} \text { has even number of a's and even number of } \mathrm{b}^{\prime} \mathrm{s}\right\}$

2.a. Define NDFSM. Convert the following NDFSM to its equivalent DFSM.

2.b. Minimize the following DFSM.

3.a.i. Define Regular expression and write Regular expression for the following language. $\mathrm{L}=\left\{\mathrm{a}^{2 \mathrm{n}} \mathrm{b}^{2 \mathrm{m}} | \mathrm{n} \geq 0, \mathrm{m} \geq 0\right\}$

3.a.ii. $\mathrm{L}=\left\{\mathrm{a}^{\mathrm{n}} \mathrm{b}^{\mathrm{m}} | \mathrm{m} \geq 1, \mathrm{n} \geq \mathrm{I}, \mathrm{nm} \geq 3\right\}$

3.b. Obtain the Regular expression for the following FSM.

4.a. i) Define a Regular grammar. Design regular grammars for the following languages.

ii) Strings of a’s and b’s having strings without ending with ab.

iii) Strings of 0’s and 1’s with three consecutive 0’s.

4.b. State and prove pumping theorem for regular languages.

5.a. i) $\mathrm{L}=\left\{0^{\mathrm{m}} 1^{\mathrm{m}} 2^{\mathrm{n}} | \mathrm{m} \geq 0, \mathrm{n} \geq 0\right\}$

ii) $\mathrm{L}=\left\{\mathrm{a}^{\mathrm{i}} \mathrm{b}^{j} | \mathrm{i} \neq \mathrm{j}, \mathrm{i} \geq 0, \mathrm{j} \geq 0\right\}$

iii) $\mathrm{L}=\left\{\mathrm{a}^{\mathrm{n}} \mathrm{b}^{\mathrm{n}-3} | \mathrm{n} \geq 3\right\}$

5.b. Consider the grammar G with production.

$\mathrm{S} \rightarrow \mathrm{AbB}$

$\mathrm{A} \rightarrow \mathrm{aA} | \in$

$\mathrm{B} \rightarrow \mathrm{aB}|\mathrm{bB}| \in$

Obtain leftmost derivation , rightmost derivation and parse tree for the string aaabab.

6.a. Define a PDA. Obtain a PDA to accept

$\mathrm{L}=\left\{\mathrm{a}^{\mathrm{n}} \mathrm{b}^{\mathrm{n}} | \mathrm{W} \in\{\mathrm{a}, \mathrm{b}\}^{*}\right\}$ . Draw the transition diagram

6.b. Convert the following grammar into equivalent PDA.

$\mathrm{S} \rightarrow \mathrm{a} \mathrm{ABC}$

$\mathrm{A} \rightarrow \mathrm{aB} | \mathrm{a}$

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

$\mathrm{C} \rightarrow \mathrm{a}$

7.a. State and prove pumping lemma for context free languages. Show that

$\mathrm{L}=\left\{\mathrm{a}^{\mathrm{n}} \mathrm{b}^{\mathrm{n}} \mathrm{c}^{\mathrm{n}} | \mathrm{n} \geq 0\right\}$ is not context free.

7.b. Explain Turing machine model.

8.a. Design a Turing machine to accept the language $\mathrm{L}=\left\{0^{\mathrm{n}} 1^{\mathrm{n}} 2^{\mathrm{n}} | \mathrm{n} \geq 1\right\}$ .

8.b. Design a Turing machine to accept strings of a’s and b’s ending with ab or ba.

9.a. Explain the following :

i) Non deterministic Turing machine

ii) Multi– tape Turing machine.

9.b. Define the following : i) Recursively enumerable language

ii) Decidable language

9.c. What is Post correspondence problem?

10.a. What is Halting problem of Turing machine?

10.b. Define the following :

i) Quantum computer

ii) Class NP

10.c. Explain Church Turing Thesis.