Question Paper: Automata Theory Question Paper - December 2016 - Information Technology (Semester 4) - Mumbai University (MU)
0

## 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 an abbn, 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 a2nbn 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 0n 1n 2n, 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

question paper mu • 138 views