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={aⁿb^mc¹|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={a^mbⁿc^m+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={(A₁, A₂, A₃), (a, b), (P, A₁}
Where, P consist of the Following Productions:
A₁→A₂A₃
A₂→A₃A₁|b
A₃→A₁A₂|a(10 marks) 5 (a) State and Prove pumping lemma for regular languages and prove that following language is regular or not
L={aⁿbⁿI 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)