1.a. Define the following terms with example : i) Alphabet ii) Power of an alphabet iii) Concentration iv) Languages

1.b. Draw a DFA to accept strings of a's and b's ending with 'bab'.

1.c. Convert the following NDFSM Fig. Q1 (c) to its equivalent DFSM.

2.a. Draw a DFSM to accept the language,

2.b. Define distinguishable and indistinguishable states. Minimize the following DFSM,

S	0	I
A	B	A
B	A	C
C	D	B
*D	D	A
E	D	F
F	G	E
G	F	E
H	G	D

i) Draw the table of distinguishable and indistinguishable state for the automata.

ii) Construct minimum state equivalent of automata.

2.c. Write differences between DFA, NFA and $\mathrm{E}-\mathrm{NF} A$

3.a. Consider the DFA shown below:

States	0	1
$\rightarrow q_{1}$	$q_{2}$	$q_{1}$
$q_{2}$	$q_{3}$	$q_{1}$
*$q_{3}$	$q_{3}$	$q_{2}$

Obtain the regular expression $R_{i j}^{(0)}$ , $R_{i j}^{(1)}$ and simplify the regular expressions as much as possible.

3.b. Give Regular expressions for the following languages on $\sum=\{a, b, c\}$ i) all strings containing exactly one a

ii) all strings containing no more than 3 a's.

iii) all strings that contain at least one occurance of each symbol in $\sum$

3.c. Let L be the language accepted by the following finite state machine.

Indicate for each of the following regular expressions, whether it correctly describes L :

i) $(a \cup b a) b b^{*} a$

ii) $(\varepsilon \cup b) a\left(b b^{*} a\right)^{*}$

iii) ba $\cup a b^{*} a$

iv) $(a \cup b a)\left(b b^{*} a\right)^{+}$

4.a. Prove that the following language is not regular : L = ${0^{n} 1^{u} | n\gt0 \}$

4.b. If $\mathrm{L}_{1}$ and $\mathrm{L}_{2}$ are regular languages then prove that $\mathrm{L}_{1} \cup \mathrm{L}_{2}$ , $\mathbf{L}_{1}, \mathbf{L}_{2}$ and $\mathbf{L}_{1}^{*}$ are regular languages.

4.c. Is the following grammar is ambiguos?

$\mathrm{S} \rightarrow \mathrm{iC}+\mathrm{S}|\mathrm{iC}+\mathrm{SeS}| \mathrm{a}$

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

5.a. Define Grammar, Derivation, Sentential forms an d give one example for each.

5.b. What is CNF ? Obtain the folloeing grammar in CNF

$\mathrm{S} \rightarrow \mathrm{ASB} | \varepsilon$

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

$\mathrm{B} \rightarrow \mathrm{SbS}|\mathrm{A}| \mathrm{bb}$

5.c. Let G be the grammar,

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

$\mathrm{A} \rightarrow \mathrm{a}|\mathrm{aS}| \mathrm{bAA}$

$\mathrm{B} \rightarrow \mathrm{b}|\mathrm{bS}| \mathrm{aBB}$

For the string aaabbbabbba find a

i) Left most derivation.

ii) Right most derivation

iii)Parse tree

6.a. Explain the following terms:

i) Pushdown automata (PDA).

ii) Languages of a PDA.

iii) Instantaneus description of a PDA.

6.b. Construct a PDA to accept the language

Draw the graphical representation of this PDA. Show the moves made by this PDA for the string aabbaa.

6.c. Convert the following CFG to PDA

$S \rightarrow a A B B |$ aAA

$A \rightarrow a B B | a$

$B \rightarrow b B B | A$

$C \rightarrow a$

7.a. If $L_{1}$ and $L_{2}$ are context free languages then prove that $\mathrm{L}_{1} \cup \mathrm{L}_{2}, \mathrm{L}_{1} \cdot \mathrm{L}_{2}$ and $\mathrm{L}_{1}^{*}$ are context free languages

7.b. Give a decision procedure to answer each of the following question:

i) Given a regular expression $\alpha$ and a PDA $M$ , the language accepted by M a subject of the language generated by $\alpha$ ? ii) GIven a context-free Grammar G and two strings $\mathrm{S}_{1}$ and $\mathrm{S}_{2}$ , does G generate $\mathrm{S}_{1} \mathrm{S}_{2}$ ? iii) GIven a context free Grammar G, does G generate any even length strings. iv) Given a Regular Grammar G, is L(G) context-free ? \lt/div\gt \ltspan class='paper-ques-marks'\gt(12 marks)\lt/span\gt \ltspan class='paper-page-id'\gt00\lt/span\gt \lt/div\gt **OR** \ltDIV class='paper-question'\gt \ltDIV class='paper-ques-desc'\gt \ltb\gt8.a.\lt/b\gt Explain with neat diagram, the working of a Turning Machine model. \lt/div\gt \ltspan class='paper-ques-marks'\gt(5 marks)\lt/span\gt \ltspan class='paper-page-id'\gt00\lt/span\gt \lt/div\gt \ltDIV class='paper-question'\gt \ltDIV class='paper-ques-desc'\gt \ltb\gt8.b.\lt/b\gt Design a Turning machine to accept the language $L=\left{a^{a} b^{\prime} c^{k} | n>=1}right.$ . Draw the transition diagram. Show the moves made by this turing machine for the string aabbcc.

9. Write short notes on :

a. Multi-tape turing machine.

b. Non-deterministic turing machine.

c. Linear Bounded automata.

10. Write shrt notes on :

a. Undecidable languages.

b. Halting problem of turing machine.

c. The post correspondence problem.