STUPIDSID
1(a)
Design a DFA to accept string over the alphabet \(\sum\)={a,b} containing even number of 'a' s.
5 M
1(b)
Let G be the grammar.Find the leftmost derivation,rightmost derivation and parse tree for the expression a*b*+a*b
G:S-->S+S|S*S
S-->a|b
G:S-->S+S|S*S
S-->a|b
5 M
1(c)
Give formal definition of a push Down automata(PDA)
5 M
1(d)
State and explain closure properties of regular languages.
5 M
2(a)
Design a DFA to accept
Binary strings in which every 0 is followed by 11
String over the binary alphabet that do not contain the substring 010.
Binary strings in which every 0 is followed by 11
String over the binary alphabet that do not contain the substring 010.
10 M
2(b)
Design a Mealy machine over the alphabet {0,1}which output EVEN,ODD according to the number of 1's encountered as even or odd.
10 M
3(a)
Using pumping lemma prove that the following language is not regular
L={ww|w e{0,1}*}
L={ww|w e{0,1}*}
10 M
3(b)
Design a NFA for accepting input strings that contain either the keyword 000 or the keyword 010 and convert it into an equivalent.
10 M
4(a)
Construct a PDA accepting the following languages L={anbman|m,n>=1}
10 M
4(b)
Design a Turing machine to recognize the language L={anbnan|n>=1}
10 M
5(a)
Explain algorithm for the conversation of a Context free grammar (CFG)to Chomsky Normal Form (CNF)and it to convert the following CFG to CNF
S-> bA|aB
A-> bAA|aS|a
B-> aBB|bs|b
S-> bA|aB
A-> bAA|aS|a
B-> aBB|bs|b
10 M
5(b)
Convert the following Context free grammar to GNF
S->AB|BC
A-> AB|a
B->AA|CB|b
C->a|b
S->AB|BC
A-> AB|a
B->AA|CB|b
C->a|b
10 M
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)
Chomsky Hierarchy
10 M
6(d)
Recursive and recursively enumerable languages.
10 M
More question papers from Automata Theory