Mumbai University Previous year question papers
V Sem CSE Examination Dec 2012
Theory of Computer Science
N.D. : (l) Question No.1 is compulsory.
(2) Attempt any fou!” questions from remaining silo. questions.
(3) Draw suitable diagrams wherever necessary.
(4) Assume suitable data, if necessary.
(a) What is finite automation? Give the finite automation M accepting (a,b)*(baaa). 5
(b) Explain C~omsky H!erarchy with languages used, forms of productions in grammars and accepting device.
(c) Differentiate Moore and Me~ly machine. 5
(d) Give and explain ambiguous context free language. 5
2. (a) Design finite state,machine to add 2 binary numbers of equal length. 10,
(b) Give the rules for defining languages assoCiated,with any regular expression:
to Let Ll‘= all words beginning with, a –L2= all words ending with a , what is L1 intersection L2 ?
3. (a) Give the statement for pumping Lemma for regular languages.
(b) Construct an NFA-I\ for – 8
(i) (00+ 1) * (10)* •
(ii) ((0 + 1)* 10 + (00)*(11 )*)*
(c) Let G be the grammar 10
S ~ aB
B ~ bibS
Find the leftmost derivation, right most derivation and parse tree for the string “bbaaabbaba”.
4. (a,) What is TM ? Give the power of TM ~ver, FSM. Explain tindecidebility and incompleteness in Turing machine.
(b) Explain PDA and power of PDM. Also design the NPDA for the given – , . 10
5. (a) Explain basic Complexity classes. 6
(b) Define NP-hard and NP-complete languages. 4
(c) Using pumping lemma, check whether an b l1 is regular or not. 10
6. (a) How regular expression is converted to DFA ? Explain aU rules with example. 10
(b) Construct a PDA accepting the language of Palindromes. 10
7. _Write short notes on (any f~ur) ;-
(a) Myhill Nerode Theorem
(b) Universal TM
(c) Rice Theorem
(d) Closure properly and
decision algorithm for CFL
(e) Application areas ofRE, FA,.PDA, CFG,TM