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

Automata Theory - May 2013

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.
1 (a) Define the following terms:
(i) Undecidability
(ii) Unrestricted Grammer
(iii) Pumping Lemma
(5 marks)
1 (b) Define TM and give its variants. (5 marks) 1 (c) Explain Chomsky hierarchy for formal languages.(5 marks) 1 (d) Give the closure properties of regular languages.(5 marks) 2 (a) (i) What is ambiguous CFG? Give one example.(ii) What is Myhill-Nerode theorem? Explain necessity of it.(10 marks) 2 (b) Let G be the grammar, find the leftmost derivation, rightmost derivation and parse tree for the string 00110101
S → 0B/1A
A → 0/0S/1AA
B → 1/1S/0BB
(10 marks)
3 (a) Explain CNF and GNF with example.(10 marks) 3 (b) Give the formal definition of RE and Design DFA consisting of (a+b)aba( a + b )(5 marks) 3 (c) Using pumping lemma prove L = {anbn | n≥1} is not regular or not.(5 marks) 4 (a) Write NFA for accepting (a+bb)(ba+ ∈)(10 marks) 4 (b) Explain DPDA and NPDA with languages of them. (10 marks) 5 (a) Find the languages defined by the following grammar:
(i) S→OA/IC
A→OS/IB/∈
B→1A/OC
C→OB/1S
(ii) S→OA/IC
A→OS/IB
B→OC/IB/∈
C→OB/IS
(10 marks)
5 (b) Construct PDA of accepting the following language L = {anbman | m,n≥1}(10 marks) 6 (a) Differentiate between Moore and Mealy machine with proper example and usage. Carry out comparison of Moore MIC to Mealy MIC.(10 marks) 6 (b) Design a Turing Machine to accept the language L = {anbn | n≥1}(10 marks)


Write short notes on (any four)

7 (a) Recursive and recursively enumerable languages.(5 marks) 7 (b) Intractable Problems(5 marks) 7 (c) Simplification of CFGs(5 marks) 7 (d) Decision properties of regular languages.(5 marks) 7 (e) Rice Theorem.(5 marks)

1  upvotes

Next up

Read More Questions

If you are looking for answer to specific questions, you can search them here. We'll find the best answer for you.

Search

Study Full Subject

If you are looking for good study material, you can checkout our subjects. Hundreds of important topics are covered in them.

Know More