1
1.1kviews
Automata Theory : Question Paper May 2014 - Information Technology (Semester 4) | Mumbai University (MU)
1
0views

## 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|S
S
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={anbman|m,n>=1}(10 marks) 4(b) Design a Turing machine to recognize the language L={anbnan|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)