## Automata Theory - Dec 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)** Explain Chomsky hierarchy.(10 marks)
**1(b)** Let G be the grammar.Find the leftmost derivation,rightmost derivation and parse tree for the string 001222

G:S$\rightarrow$0s|1A|2B| $\epsilon$

A$\rightarrow$1A|2B|$\epsilon$

B$\rightarrow$2B|$\epsilon$(10 marks)
**2(a)** Design a DFA that reject any string over (0,1,2)where 2 is immediately preceded by a 0.It should accept all other strings.(10 marks)
**2(b)** Design a DFA for the regular expression (a+b)*aba**(10 marks)
** 3(a) Design a mealy machine to accept all string ending with 00 or 11(10 marks)
3(b) Convert the following NFA to a reduce DFA (Final state is marked with*)

δ | 0 | 1 |

P | p q | p |

q | r | r |

r | s | - |

s |
s | s |

**4(a)**

Using pumping lemma prove that the following languages is not regular L=|ww|w $\epsilon${0,1}}

(10 marks)**4(b)**Design Turing machine to generate the language given by a regular expression 00*(10 marks)

**5(a)**(i)Covert the following CFG to CNF

S$\rightarrow$aAbB

A$\rightarrow$aA|a

B$\rightarrow$bB|b

(ii)Construct a CFG over{a,b}to accept a set of all palindromes.(10 marks)

**5(b)**Design a PDA corresponding to the grammar S$\rightarrow$aSa|bSb|$\epsilon$ (10 marks)

### any two

**6(a)** Write short notes on

variant of a Turning Machine(10 marks)
**6(b)** Post Correspondence problem(10 marks)
**6(c) ** Halting Problem'(10 marks)
**6(d) ** Pumping Lemma for Regular languages(10 marks)