STUPIDSID
1(a)
Explain Chomsky hierarchy.
10 M
1(b)
Let G be the grammar.Find the leftmost derivation,rightmost derivation and parse tree for the string 001222
G:S\(\rightarrow\)0s|1A|2B| \(\epsilon\)
A\(\rightarrow\)1A|2B|\(\epsilon\)
B\(\rightarrow\)2B|\(\epsilon\)
G:S\(\rightarrow\)0s|1A|2B| \(\epsilon\)
A\(\rightarrow\)1A|2B|\(\epsilon\)
B\(\rightarrow\)2B|\(\epsilon\)
10 M
2(a)
Design a DFA that reject any string over (0,1,2)where 2 is immediately preceded by a 0.It should accept all other strings.
10 M
2(b)
Design a DFA for the regular expression (a+b)*aba
10 M
3(a)
Design a mealy machine to accept all string ending with 00 or 11
10 M
3(b)
Convert the following NFA to a reduce DFA (Final state is marked with*)
| δ | 0 | 1 |
| P | p q | p |
| q | r | r |
| r | s | - |
| *s | s | s |
10 M
4(a)
Using pumping lemma prove that the following languages is not regular L=|ww|w \(\epsilon\){0,1}*}
10 M
4(b)
Design Turing machine to generate the language given by a regular expression 00*
10 M
5(a)
(i)Covert the following CFG to CNF
S\(\rightarrow\)aAbB
A\(\rightarrow\)aA|a
B\(\rightarrow\)bB|b
(ii)Construct a CFG over{a,b}to accept a set of all palindromes.
S\(\rightarrow\)aAbB
A\(\rightarrow\)aA|a
B\(\rightarrow\)bB|b
(ii)Construct a CFG over{a,b}to accept a set of all palindromes.
10 M
5(b)
Design a PDA corresponding to the grammar S\(\rightarrow\)aSa|bSb|\(\epsilon\)
10 M
any two
6(a)
Write short notes on
variant of a Turning Machine
variant of a Turning Machine
10 M
6(b)
Post Correspondence problem
10 M
6(c)
Halting Problem'
10 M
6(d)
Pumping Lemma for Regular languages
10 M
More question papers from Automata Theory