## Automata Theory - May 2012

### 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)** State and Prove the pumping lemma for the regular grammar.(5 marks)
**1 (b)** Explain different types of techniques for Turing Machine Construction.(5 marks)
**1 (c)** Compare and Contrast Mealy Machine and Moore Machine(5 marks)
**1 (d)** Prove that it is undecidable whether context free grammar is ambiguous.(5 marks)
**2 (a)** Write a regular expression for the following languages:

i. The set of all the strings such that the number of 0's is odd.

ii. The set of all the strings that do not contain 1101(10 marks)
**2 (b)** Convert the following NFA to DFA P is the initial state r and s it the final state.

δ |
0 |
1 |

→ p | {p,r} | {q} |

q | {r,s} | {p} |

r | {p,s} | {r} |

s | {q,r} | {} |

**3 (a)**Show that every regular language is a context free language.

HINT: Construct a CFG by induction on the number of operators in the regular expression.(10 marks)

**3 (b)**A palindrome is a string that equals its own reverse, such as 0110 or 1011101. Use pumping lemma to show that set of palindromes is not regular language.(10 marks)

**4 (a)**Design a PDA to accept each of the following languages

i. {0

^{n}1

^{m}0

^{n}| m,n≥1}

ii. {0

^{n}1

^{m}0

^{m}0

^{n}| m,n≥1}(10 marks)

**4 (b)**Convert the grammar

s->0AA

A->0S|1S|0

to a PDA that accept same language by empty stack.(10 marks)

**5 (a)**S->ABC|BaB

A->Aaa|bAc|AAA

B->BbB|A|d

C->CA|AC

D->Ε

i. Eliminate ∈ production

ii. Eliminate unit production

iii. Eliminate useless symbols

iv. Put grammar in CNF(10 marks)

**5 (b)**Prove that L={a

^{n}| n is prime} is not context free.(10 marks)

**6 (a)**Design Turning Machine for the following language.

"set of all strings of balanced parenthesis"(10 marks)

**6 (b)**Convert the following grammar to Gribach normal form

S→AB1|0

A→00A|B

B→|A|(10 marks)

**7 (a)**Myhill-Nerode theorem.(5 marks)

**7 (b)**Post Correspondence Problem.(5 marks)

**7 (c)**Universal Turning Machine.(5 marks)

**7 (d)**The Classes P and NP. (5 marks)