Theory of Computer Science : Question Paper May 2012 - Computer Engineering (Semester 5)

3views

written 8.1 years ago by

Theory of Computer Science - May 2012

Computer Engineering (Semester 5)

TOTAL MARKS: 100
TOTAL TIME: 3 HOURS (1) Question 1 is compulsory.
(2) Attempt any four from the remaining questions.
(3) Assume data wherever 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) Begin with the grammar: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.
(14 marks) 5(b) Prove that L ={aⁿ | n is prime} is not context free.(6 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?1A|(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)

ADD COMMENT EDIT