## 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^{n}b^{n}c^{n}| 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^{n}2^{n}3^{n} | 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)