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

Automata Theory - May 2012

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) State and Prove the pumping lemma for the regular grammar.(5 marks) 1 (b) Explain different types of techniques for Turing Machine Construction.(5 marks) 1 (c) Compare and Contrast Mealy Machine and Moore Machine(5 marks) 1 (d) Prove that it is undecidable whether context free grammar is ambiguous.(5 marks) 2 (a) Write a regular expression for the following languages:
i. The set of all the strings such that the number of 0's is odd.
ii. The set of all the strings that do not contain 1101
(10 marks)
2 (b) Convert the following NFA to DFA P is the initial state r and s it the final state.

δ 0 1
→ p {p,r} {q}
q {r,s} {p}
r {p,s} {r}
s {q,r} {}
(10 marks) 3 (a) Show that every regular language is a context free language.
HINT: Construct a CFG by induction on the number of operators in the regular expression.
(10 marks)
3 (b) A palindrome is a string that equals its own reverse, such as 0110 or 1011101. Use pumping lemma to show that set of palindromes is not regular language.(10 marks) 4 (a) Design a PDA to accept each of the following languages
i. {0n1m0n | m,n≥1}
ii. {0n1m0m0n | m,n≥1}
(10 marks)
4 (b) Convert the grammar
s->0AA
A->0S|1S|0
to a PDA that accept same language by empty stack.
(10 marks)
5 (a) S->ABC|BaB
A->Aaa|bAc|AAA
B->BbB|A|d
C->CA|AC
D->Ε
i. Eliminate ∈ production
ii. Eliminate unit production
iii. Eliminate useless symbols
iv. Put grammar in CNF
(10 marks)
5 (b) Prove that L={an | n is prime} is not context free.(10 marks) 6 (a) Design Turning Machine for the following language.
"set of all strings of balanced parenthesis"
(10 marks)
6 (b) Convert the following grammar to Gribach normal form
S→AB1|0
A→00A|B
B→|A|
(10 marks)
7 (a) Myhill-Nerode theorem.(5 marks) 7 (b) Post Correspondence Problem.(5 marks) 7 (c) Universal Turning Machine.(5 marks) 7 (d) The Classes P and NP. (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