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)