# Mumbai University Previous year question papers

## V Sem CSE Examination Dec 2007

## Theory of Computer Science

Q. No.1 a) Design the DFA which accepts set of strings such that every string containing 00 as a substring but no~qqO,asa substring.

b)(i)Prove that

L = { 01}J2’3J I i >=}and»=1} is not contextfree. (08)

(ii)Showthat 0(0+1)’+(0+1)’00 (0+1)= (1’0) ‘(O}’)’. (04)

Q.No.2a) Convertthe given grammar to grebaic normal form

S~ aSB

I aA

A-?Aa

I Sa I

a

b) Design the turing machine to find the value of log2nwhere n is any binary number and a perfect square.

.

Q.No.3 a) Designthe push down automata to accept language containing all odd length palindromesover * L *= {O,]}. ‘

b) Prove that it is undecidable whether Context free grammar is ambiguous.

Q.No4.a) Stateandprovepumpinglemmafor regularlanguagesandprovethat Lpr consisting of all strings of} ‘s whose length is prime is not regular.

b) Design finite state machine that compares two binary numbers to determine whether they are equal and which ofthe two are larger.

Q.No.5 -a) i) Determine thlut’ for foil f Post correspondence problem.(05)

ii) Write note on ‘Post Machine’.

b) i) Write note on ‘Multitape Turing machine’.

ii)Designmealy machine to find 2’s complement of binary.number.

Q.No.6 a)Coostruct DFA equivalent to NFA ({p,q,r,s}, {O,]},ON.p, {q,s}) where ONis given (] 0) In following table.

b) i) Write note on ‘Universal turing machine’.

ii) Provethat if Land Mare regular languages then L-M is also regular.

Q.No.7 a) Write regular expressions for following languages.

i) L = { a”bm: (n+m) is even}

ii) L = { w € (a,b)* : (number of a’s in w) mod 3 = 0 }

b) Construct context free grammar equivalent to following PDA

o(qo,b, Zo) = {(qo. ZZo)}

o(qo.€, Zo) = {( qo.E)}

o(qo.b, Z) = {(.qo.ZZ)}

o(qo.a, Z) = {( ql. Z)}

8(ql. b, Z) = {( qo.E)}

8(ql. a, Zo) = {( qo,Zo)}

c) Write short notes on any two.

i) Myhill Nerode Theorm.

ii) Halting Problem.

iii) Grebaic Theorm.

OWIn Instance 0

ListA List B