## Automata Theory - December 2016

### MU Information Technology (Semester 4)

Total marks: --

Total time: --
INSTRUCTIONS

(1) Assume appropriate data and state your reasons

(2) Marks are given to the right of every question

(3) Draw neat diagrams wherever necessary
**1(a)** State applications where Automata Theory is used.
5 marks

**1(b)** What are limitations of finite automata.
5 marks

**1(c)** Develop an NF A to accept stringd ending with 'aba' over {a, b}
5 marks

**1(d)** Explain with example equivalence between NFA &DFA.
5 marks

**2(a)** Consider the grammar G={S, A}, (0, 1) P, S}, where P consists of:

i) S→0AS|0 ii) A→S 1A |SS|10 Show the leftmost derivation for the input string '001100'. Is given G Ambiguous?
5 marks

**2(b)** Construct deterministic PDA to recognize a^{n} abb^{n}, 0 over {a, b}
5 marks

**3(a)** Define Normal form and its types and Convert given grammar to CNF:

i) S→ bA |aB ii) A →bAA |aS| a iii) B → aBB |bS| b
5 marks

**3(b)** Define CFG a construct a CFG for a^{2n}b^{n}
5 marks

**4(a)** Design mealy machine to accept all strings ending with aa or bb.
5 marks

**4(b)** Minimize given DFA-

!mage
5 marks

**5(a)** Develope ε-NFA to accept 0^{n} 1^{n} 2^{n}, where n >=0 over {0, 1, 2}
5 marks

**5(b)** Define Halting problem.
5 marks

**5(c)** Give Regular Expressions for-

i) Binary strings containing atleast one 11 & atleast one 00

ii) Strings with even number of a's

iii) Strings in which third symbol from end is 'c' over {a, b, c}
5 marks

**5(d)** Describe Regular Language for given Regular Expressions

i) (ab + ba)*

ii) 1 (0 +1) (0+1) (0 +1)* 0
5 marks

**6(a)** Write short note on - Chosmsky Hierarchy
5 marks

**6(b)** Explain Post correspondence problem.
5 marks

**6(c)** Explain Pumping Lemma for Regular Language.
5 marks