0
1.4kviews
Theory of Computer Science : Question Paper May 2013 - Computer Engineering (Semester 5) | Mumbai University (MU)

## Theory of Computer Science - May 2013

### 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) 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.(5 marks) 2(a) (ii) What is Myhill-Nerode theorem? Explain necessity of it. (5 marks) 2(b) Let G be the grammar, find the leftmost derivation, rightmost derivation and parse tree for the string 00110101S ? 0B/1AA ? 0/0S/1AAB ? 1/1S/0BB(10 marks) 3 (c) Using pumping lemma prove L = {anbn | n>=1} is not regular or not.(5 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) 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/ICA?OS/IB/? B?1A/OCC?OB/1S(ii) S?OA/ICA?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 = {an bn | n>=1 }(10 marks) 7 (c) Simplification of CFGs(5 marks)

### Write short notes on any FOUR:-

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