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={aⁿbⁿcⁿ| 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={1ⁿ2ⁿ3ⁿ | 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={WW^R|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)