# Mumbai University Previous year question papers

## V Sem CSE Examination June 2006

## Theory of Computer Science

N.B. : (1) ‘()Jest ion No.1 is coIIpllsory.

(2) A~tempt any four questions out of remaining six,questions.

(3) Assumptions made should be clearly stated.

(4) ,Ass’:1IIle suitable data wherever required but justify the same.

(5) Fi<J1:1res to the right indicate full marks.

La) Design the finite state mpchine that compares two binarr numbers to

determine whetherthey are equal and which of the two I~

* I*c1..Yj fJ-“”,

b)(i)State.and prove the pumping lemmafor context nee languages. (08)

(ii)Convertthe following regular expressionto NFA with e transitiQns. (04)

R= (1(00)*1+01.*0)*

(08)

7.a) Prove the following:

–

, (i) L

={aP I p is prime}is notcontextnee.

(ii)L

={ (ab) n ak : n>k, k~O} is not regular.

b) Consider the following grammar:

–

.

S~ASB

I e

A -taAS

I

a

B-tSb&

I A I bb

Put the above grammarin Chomskynormal form.

(10)

(10)

J. a) Give the DFA accepting the following language over alphabet {O,I } (08)

L = ‘Set of all strings beginning with I that, when interpreted as a binary

integer, is a multiple of5: for example, strings 101,1010, and 1111 in the

language; 0, 100, and

t II

not.

b) (i) Design turing machille that can accept the set of all even palindromes (08)

over alphabet {0,1}

(ii) Show that that

(1+00*1)+ (1+00*1)(0+10*1) * (OHO*l)

=

0*1(0+ 10*1) *

4. a) Construct the PDA equivalent to the following context free grammar. (10)

S-+ OaB

B-t OSlIS I 0

Test whether 0104 is in language.

(04)

..,

b)Provethat it is undecidablewhether a context free grarnmaris ambiguous.(IO)

5. a) Convertthe followinggramrnarinto Grebaicnormal form.

. S-t XY1

I 0

X~ OOX

IY

Y–IXI

(10)

b) Design turing machine to recognize the language L = {I n2n3n

I

n2:I} (10)

6. a) Designthe PDAthat will recognizethe languageL = WWR:Wis in (10)

{a,b}* i,e even length palindrome over

I = {a,b}.

b) Give the moore and mealy machinefor the following (10)

For the input nom

*l:*, *where *L *= {0,1,2},printthe residu modulo 5

of the input treated as ternary..

www.stupidsid.com

7.a) Write regular expressions for the following languages

i)’L = {O,l}containing all possible combinations of D’s and l’s but

not having two consecutive O’s.

ii) The set of all strings ofO’s and l’s such that every pair of adjacent O’s

appears before any pair of adjacent 1’so

iii)The set of all strings over

*L *= {O,l}without length two.

b) i) Verify the following identities involving regular expressions.

.

(R+S)+T=R+(S+T)

(RS)T

=

R(ST)

ii) Write short notes on any two

(i) Grebaic Theorm.

(ii) P<?stcorrespondence problem.

(iii) Myhill-Nerode’s Theorm.

(06)

.

(06)

(08)

w