# Mumbai University Previous year question papers

## V Sem CSE Examination June 2008

## Theory of Computer Science

N.S.: (1) Question No.1 is compulsory.. .

(2) Attempt any four questions out of remaining six questions.

(3) Assumptions made should be clearly stated.

(4) Figures to the right indicate full marks.

(5) Assume suitable data wherever required but justify the same.

Q. No.1 a) Prove that

i) L={ (ab)nak I n>k, k>=O}is notregular.

ii) L={ anbncnI n>=1 } is not context free.

Q.No.2a) Convert the following grammar in chomsky normal form

AACD

A~aAbr€

C~aCra

D~ aDa r bDb I€

b) Design the turing machine to recognize the language L={ anbncnI n>=1 } 10

Q.No.3 a) Prove that every nontrivial property of the RE languages is undecidable.

b) Design the PDA for the language L={ wcwr w€{a,b}.}

.Q. No.4 a) Convert the following grammar in grebaic normal form

s~AAlo

A~ SS 11

b) Design tnoore machine to convert each occurrence of substring 1000DY. 1001.

Q.No.5 a) Convert the following expression grammar to PDA.

b).Write regularexpressionfor the followinglanguages.

J) L={ anbmI n>=4, m<=3} ii) L={ w: Iwlmod 3 = 0, w€{a,bf}

c) Write note on ‘Universal turing machine’

Q. No.6 a) pesign TM which will recognize strings containing equal number of ‘O’s and ‘1 ‘ s. .

b) Design the DFA for the language, contains strings in which leftmost symbol differ from rightmost symbol.

* L *is given {O,I }

Q. No.7 a) Design FSM for binary adder.

b) Write short note on any two.

(i) Post Corr~spondence Problem.

(ii) Myhill-Nerode’s Theorm.

(Hi)Halting problem.