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

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)

1  upvotes

Next up

Read More Questions

If you are looking for answer to specific questions, you can search them here. We'll find the best answer for you.

Search

Study Full Subject

If you are looking for good study material, you can checkout our subjects. Hundreds of important topics are covered in them.

Know More