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

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)