# 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.

1.

(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

IbA

A~al as

I bAA

B ~ bibS

I aBB

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

CFG

S~aAA

A~bS

A~aS

S~a

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