## Automata Theory - May 2013

### 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)** Define the following terms:

(i) Undecidability

(ii) Unrestricted Grammer

(iii) Pumping Lemma(5 marks)
**1 (b)** Define TM and give its variants. (5 marks)
**1 (c)** Explain Chomsky hierarchy for formal languages.(5 marks)
**1 (d)** Give the closure properties of regular languages.(5 marks)
**2 (a)** (i) What is ambiguous CFG? Give one example.(ii) What is Myhill-Nerode theorem? Explain necessity of it.(10 marks)
**2 (b)** Let G be the grammar, find the leftmost derivation, rightmost derivation and parse tree for the string 00110101

S → 0B/1A

A → 0/0S/1AA

B → 1/1S/0BB(10 marks)
**3 (a)** Explain CNF and GNF with example.(10 marks)
**3 (b)** Give the formal definition of RE and Design DFA consisting of (a+b)*aba( a + b )*(5 marks)
**3 (c)** Using pumping lemma prove L = {a^{n}b^{n} | n≥1} is not regular or not.(5 marks)
**4 (a)** Write NFA for accepting (a+bb)*(ba*+ ∈)(10 marks)
**4 (b)** Explain DPDA and NPDA with languages of them. (10 marks)
**5 (a)** Find the languages defined by the following grammar:

(i) S→OA/IC

A→OS/IB/∈

B→1A/OC

C→OB/1S

(ii) S→OA/IC

A→OS/IB

B→OC/IB/∈

C→OB/IS(10 marks)
**5 (b)** Construct PDA of accepting the following language L = {a^{n}b^{m}a^{n} | m,n≥1}(10 marks)
**6 (a)** Differentiate between Moore and Mealy machine with proper example and usage. Carry out comparison of Moore MIC to Mealy MIC.(10 marks)
**6 (b)** Design a Turing Machine to accept the language L = {a^{n}b^{n} | n≥1}(10 marks)

### Write short notes on (**any four**)

**7 (a)** Recursive and recursively enumerable languages.(5 marks)
**7 (b)** Intractable Problems(5 marks)
**7 (c)** Simplification of CFGs(5 marks)
**7 (d)** Decision properties of regular languages.(5 marks)
**7 (e)** Rice Theorem.(5 marks)