## Automata Theory - May 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)** Design a DFA to accept string over the alphabet $\sum$={a,b} containing even number of 'a' s.
(5 marks)
**1(b)** Let G be the grammar.Find the leftmost derivation,rightmost derivation and parse tree for the expression a*b*+a*b
G:S-->S+S|S*S

S-->a|b (5 marks)

**1(c)**Give formal definition of a push Down automata(PDA)(5 marks)

**1(d)**State and explain closure properties of regular languages.(5 marks)

**2(a)**Design a DFA to accept

Binary strings in which every 0 is followed by 11

String over the binary alphabet that do not contain the substring 010.(10 marks)

**2(b)**Design a Mealy machine over the alphabet {0,1}which output EVEN,ODD according to the number of 1's encountered as even or odd.(10 marks)

**3(a)**Using pumping lemma prove that the following language is not regular

L={ww|w e{0,1}*}(10 marks)

**3(b)**Design a NFA for accepting input strings that contain either the keyword 000 or the keyword 010 and convert it into an equivalent.(10 marks)

**4(a)**Construct a PDA accepting the following languages L={a

^{n}b

^{m}a

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

**4(b)**Design a Turing machine to recognize the language L={a

^{n}b

^{n}a

^{n}|n>=1}(10 marks)

**5(a)**Explain algorithm for the conversation of a Context free grammar (CFG)to Chomsky Normal Form (CNF)and it to convert the following CFG to CNF

S-> bA|aB

A-> bAA|aS|a

B-> aBB|bs|b (10 marks)

**5(b)**Convert the following Context free grammar to GNF

S->AB|BC

A-> AB|a

B->AA|CB|b

C->a|b (10 marks)

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

variant of a Turning Machine(10 marks)

**6(b)**Post Correspondence problem(10 marks)

**6(c)**Chomsky Hierarchy(10 marks)

**6(d)**Recursive and recursively enumerable languages.(10 marks)