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

Automata Theory - Dec 2015

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.


Solve any five.

1 (a) Explain if the following machine M is a DFA? Is it NFA? Write formally a definition for this M. (4 marks) 1 (b) Design moore machine to convert each occurrence of 100 to 101.(3 marks) 1 (c) Write a CFG to generate strings Starting and ending with different letter over the ∑={a, b}(3 marks) 1 (d) What is Multi-Tape Turing Machine.(3 marks) 1 (e) Difference between FA and PDA.(4 marks) 1 (f) Give a regular expression for the language over the alphabet ∑={a, b} containing at most two a's.(3 marks) 2 (a) Construct a minimal DFA which accepts L={anbmc1|n,mm|>=O}(5 marks) 2 (b) State and explain Turing Machine Formalism 5.(5 marks) 2 (c) If L(r)= {aaa, aab, aba, abb, baa, bab, bba, bbb}, find the regular expression r which represents L(r).(5 marks) 2 (d) Explain Chomsky Hierarchy.(5 marks) 3 (a) Construct a TM for accepting palindromes.(10 marks) 3 (b) Design PDA For recognizing L={ambncm+n| m,n>=1}.(10 marks) 4 (a) Convert the following grammer 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) Convert the followng Grammer G to GNF.
G={(A1, A2, A3), (a, b), (P, A1}
Where, P consist of the Following Productions:
A1→A2A3
A2→A3A1|b
A3→A1A2|a
(10 marks)
5 (a) State and Prove pumping lemma for regular languages and prove that following language is regular or not
L={anbnI n>=1}
(10 marks)
5 (b) Construct NFA, DFA for the regular Expression R=ab(a+b)+abb. Obtain minimized DFA.(10 marks)


Write short notes on (any two).

7 (a) Simplification of CFG.(10 marks) 7 (b) Recursive and Recursively enumerable languages.(10 marks) 7 (c) Universal TM(10 marks) 7 (d) Halting Problem(10 marks)

Please log in to add an answer.