## Automata Theory - Dec 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.

### Solve any five.

**1 (a)** Explain if the following machine M is a DFA? Is it NFA? Write formally a definition for this M.
(4 marks)
**1 (b)** Design moore machine to convert each occurrence of 100 to 101.(3 marks)
**1 (c)** Write a CFG to generate strings Starting and ending with different letter over the ∑={a, b}(3 marks)
**1 (d)** What is Multi-Tape Turing Machine.(3 marks)
**1 (e)** Difference between FA and PDA.(4 marks)
**1 (f)** Give a regular expression for the language over the alphabet ∑={a, b} containing at most two a's.(3 marks)
**2 (a)** Construct a minimal DFA which accepts L={a^{n}b^{m}c^{1}|n,mm|>=O}(5 marks)
**2 (b)** State and explain Turing Machine Formalism 5.(5 marks)
**2 (c)** If L(r)= {aaa, aab, aba, abb, baa, bab, bba, bbb}, find the regular expression r which represents L(r).(5 marks)
**2 (d)** Explain Chomsky Hierarchy.(5 marks)
**3 (a)** Construct a TM for accepting palindromes.(10 marks)
**3 (b)** Design PDA For recognizing L={a^{m}b^{n}c^{m+n}| m,n>=1}.(10 marks)
**4 (a)** Convert the following grammer to Chomsky Normal Form. Show all the relevant Steps briefly.

S→bA| aB

A→ bAA|aS|a

B→aBB|bs|b(10 marks)
**4 (b)** Convert the followng Grammer G to GNF.

G={(A_{1}, A_{2}, A_{3}), (a, b), (P, A_{1}}

Where, P consist of the Following Productions:

A_{1}→A_{2}A_{3}

A_{2}→A_{3}A_{1}|b

A_{3}→A_{1}A_{2}|a(10 marks)
**5 (a)** State and Prove pumping lemma for regular languages and prove that following language is regular or not

L={a^{n}b^{n}I n>=1}(10 marks)
**5 (b)** Construct NFA, DFA for the regular Expression R=ab(a+b)+abb. Obtain minimized DFA.(10 marks)

### Write short notes on (any two).

**7 (a)** Simplification of CFG.(10 marks)
**7 (b)** Recursive and Recursively enumerable languages.(10 marks)
**7 (c)** Universal TM(10 marks)
**7 (d)** Halting Problem(10 marks)