1
Automata Theory : Question Paper May 2016 - Information Technology (Semester 4) | Mumbai University (MU)

## Automata Theory - May 2016

### 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.

### IT

1(a) What is the complement of the language accepted by the NFA shown below? Assume S={a} and c is the empty string. (2 marks) 1(b) Definition of a language L with alphabet {a} is given as following
{ an k | k > 0, and n is a positive integer constant }
What is the minimum number of states needed in a DFA to recognize L?
(2 marks)
1(c) What is Multi-Tape Turing Machine?(3 marks) 1(d) Design Mealy Machine to convert each occurrence of substring 1000 by 1001.(7 marks) 1(e) State that whether a following Language is Regular or not.
1) L = {WWR | |W|=2 over ∑={a,b}}
2) L = {WWR | Wc (a,b)*}
(6 marks)
2(a) Give formal definition of a Turing Machine.(5 marks) 2(b) Write a regular expression for the following languages, over sigma=(a,b}.
1. Seventh symbol from right must be a.
2. Every second character is b.
3. Exactly one ab.
(10 marks)
2(c) Explain Chomsky Hierarchy.(5 marks) 3(a) Construct a TM for accepting Even palindromes.(10 marks) 3(b) Design PDA For recognizing L={an b2 n+1 | n>=1}(10 marks) 4(a) Convert the following grammar to Chomsky Normal Form. Show all the relevant steps briefly.
S --->bA | aB
A --->bAA | aS | a
B ---> aBB | bS | b
(10 marks)
4(b) Give the technical strategy to convert CFG to GNF.
Convert the following grammar to GNF.
S → AA | a
A → SS | b
(10 marks)
5(a) Enumerate the differences between finite automata and non-deterministic automata?(8 marks) 5(b) Construct NFA, DFA for the regular Expression R=ab(a+b)+abb. Obtain minimized DFA.(7 marks) 5(c) Give formal definition of a Push Down Automata(PDA).(5 marks)

### Write short note on

6(a) Unsolvable problems(10 marks) 6(b) Recursive and Recursively enumerable languages.(10 marks) 6(c) Simplification of CFG.(10 marks)