STUPIDSID
1(a)
Write regular expression to denote a language L which accepts all the strings which begin or end with either 00 or 11.
5 M
1(b)
Convert the given CFG to CNF
\( S\rightarrow aSa|bSb|a|b \)/
\( S\rightarrow aSa|bSb|a|b \)/
5 M
1(c)
Difference between FA and PDA
5 M
1(d)
Design moore machine to covert each occurrence of 111 to 101.
5 M
2(a)
Construct NFA with epsilon which accept a language consisting the string of any numbers of a's followed by any number of b's followed by any number of c's Also convert it into NFA witout epilson.
10 M
2(b)
Design a DFA corresponding to regular expression (a+b)* aba(a+b)*
10 M
3(a)
Use pumping lemma prove that whether following language is regular or not \[(a^{n}b^{n}c^{n}|n>=1)\]
10 M
3(b)
Explain Chomsky's Hierarchy
10 M
4(a)
Definne context free grammar. Obtain the CFG for the following regular expression:
(110 + 11)* (10)*
(110 + 11)* (10)*
10 M
4(b)
Convert given CFG to CNF
\[&S\rightarrow ASB|\varepsilon\\ &B\rightarrow SbS|A|bb\\ &A\rightarrow aAS|a\]
\[&S\rightarrow ASB|\varepsilon\\ &B\rightarrow SbS|A|bb\\ &A\rightarrow aAS|a\]
10 M
5(a)
Design a PDA to accept the language \[\left \{ L=a^{m}b^{m}c^{n}|m,n>=1 \right \}\]
10 M
5(b)
Construct TM for \[L=\left \{ a^{n}b^{n}c^{n}|n>=1\right \}\]
10 M
Write short note any two question from Q.6(a, b, c)
6(a)
Post Correspondence Problem
10 M
6(b)
Recursive and Recursively enumerable languages.
10 M
6(c)
Halting Problem
10 M
More question papers from Automata Theory