Automata Theory - May 2014

Information Technology (Semester 4)

TOTAL MARKS: 80
TOTAL TIME: 3 HOURS (1) Question 1 is compulsory.
(2) Attempt any three from the remaining questions.
(3) Assume data if required.
(4) Figures to the right indicate full marks. 1(a) Design a DFA to accept string over the alphabet $\sum$={a,b} containing even number of 'a' s. (5 marks) 1(b) Let G be the grammar.Find the leftmost derivation,rightmost derivation and parse tree for the expression ab+ab
G:S-->S+S|SS
S-->a|b (5 marks) 1(c) Give formal definition of a push Down automata(PDA)(5 marks) 1(d) State and explain closure properties of regular languages.(5 marks) 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.(10 marks) 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 marks) 3(a) Using pumping lemma prove that the following language is not regular
L={ww|w e{0,1}*}(10 marks) 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 marks) 4(a) Construct a PDA accepting the following languages L={aⁿb^maⁿ|m,n>=1}(10 marks) 4(b) Design a Turing machine to recognize the language L={aⁿbⁿaⁿ|n>=1}(10 marks) 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 (10 marks) 5(b) Convert the following Context free grammar to GNF
S->AB|BC
A-> AB|a
B->AA|CB|b
C->a|b (10 marks) 6(a) Write short notes on
variant of a Turning Machine(10 marks) 6(b) Post Correspondence problem(10 marks) 6(c) Chomsky Hierarchy(10 marks) 6(d) Recursive and recursively enumerable languages.(10 marks)