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ⁿ abbⁿ, 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²ⁿbⁿ 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ⁿ 1ⁿ 2ⁿ, 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