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

Automata Theory - May 2015

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.


Attempt any four sub-questions.

1 (a) Design a DFA to accept only those strings containing a substring 'aa'.(5 marks) 1 (b) Design a Moore machine for binary adder.(5 marks) 1 (c) Give formal definition of a Push Down Automata.(5 marks) 1 (d) Construct a Context Free Grammar for the language with equal number of a's and b's.(5 marks) 1 (e) Give a regular expression for a language over the alphabet ?={a,b} containing at most two a's.(5 marks) 2 (a) Design a DFA that accepts the strings over a binary alphabet that do not contain the substring 010.(10 marks) 2 (b) Convert the following NFA to a reduced DFA. (10 marks) 3 (a) What is a Mealy machine. Design a mealy machine to determine the residue mod 5 of a binary number.(10 marks) 3 (b) Using pumping lemma prove that the following language is not regular
L={anbncn| n>=0}
(10 marks)
4 (a) Find a regular expression RE corresponding to the following FA. (10 marks) 4 (b) Design a Turing machine to recognize the language
L={1n2n3n | n>=1}
(10 marks)
5 (a) What is Greibach Normal Form (GNF). Convert the following CFG to GNF.
S→Sab|Sba|ε
(10 marks)
5 (b) Design a PDA for the language
L={WWR|W? {a,b}*}
(10 marks)


Write short notes on:

6 (a) Variants of Turning Machines.(10 marks) 6 (b) Recursive and Recursively enumerable languages.(10 marks) 6 (c) Chomsky Hierarchy.(10 marks) 6 (d) Halting Problem.(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