0
Theoretical Computer Science : Question Paper May 2012 - Computer Engineering (Semester 4) | Mumbai University (MU)

## Theoretical Computer Science - May 2012

### Computer Engineering (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->E
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 paranthesis (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)

0