STUPIDSID
Please log in to continue.
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→aSa|bSb|a|b/
S→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 (anbncn|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 {L=ambmcn|m,n>=1}
10 M
5(b)
Construct TM for L={anbncn|n>=1}
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