CS-501 - Theory of Computation

Convert the following Moore machine to Mealy.

i) alt=''

ii) alt=''

For $\Sigma = \{a, b\}$, construct DFA's that accept the sets consisting of

i) All the strings with exactly one 'a'.

ii) All the string with atleast one 'a'.

iii) All strings with atleast one 'a' and followed by exactly two b's.

Describe the following sets by regular expression.

i) Strings containing 1100 as substrings.

ii) The set of all strings of 0's are 1's ending with 00.

iii) ${\Lambda, a, aa, aaa, \dots}

Explain Arden's theorem and Pumping Lemma.

What is Ambiguity? Explain taking any two examples.

Design a CFG.

i) $L(G)=\{a^ib^ck \mid i \ne j \text{ (or) } j \ne k\}$

ii) $L(G)=\{a^ib^{2i} \mid i \ge 0\}$

Define a context free grammar with example.

Explain DPDA and NPDA with taking a suitable example.

Explain Recursively enumerable language and decidability.

Design a Push down automata.

i) $a^nb^{3n}, n \ge 1$

ii) $ww^R, w \in \{a, b\}^2$

Halting problem

Turing machine

Chomsky Normal form

2 way DFA