NMIMS University 2009 B.Tech Computer Science and Engineering Theoritical Computer science - Question Paper
S\ K.NJ'S NMJAJS UNAERSJ TV \1IK1.SII PA IF I SfHOOl (>lli:(HN()],OGY MANAGEMENT.
U lvch Programme (COMP) HI Year Trimester VII 200910
Subjwt: Theoretical (ornputcr Sckna Otf -\0
Max.Marks: 10U Time Allowed: 3 Hrs
a. &o 0<2
Imuuc lions:
1) (Question No 1 is conipui.voi).
2) Attempt any four question** fiom fiie remaining questions.
1 (j) Design the DFA for ihc lingiiaee.conlains strings in which leftmost Svmboln tlilfcr from rightmost symbol. is given (0, 1}
(10>
<10)
(h) Design a i.\ I which will rwiognize strings containing number of *0's and i s
>.(.]) t'omjwre and conttasl Moore and Mcalv mavlunc Design a (10)
machine to convcrt each occurrmcc of ib*hin abb by nba. {fl. b} tb) Convert the followmu grammar in rhomsky normal form. (10)
S-AAl*l>
[* i * A
laDa Nit
u) UVile .i inugiam to uan&lau .t uvular expression to limit automata. \ luj
<b) (onMtuvi . NT A for t}u' uvular expression 0] * * J and concert it to DFA. (10)
4. i'a) Prow thai it i undecidjblc whether a context free grammar is 3mbiguou&. (luj ib) Design a grammar for accepting an Kvcn Palindrome over {a,b}. (10)
5. ta) Design j lunngmuliuictoiomputcn! (10) ib) FxpJam ONF wifb -suitable example (10)
6 t>) State and prow pumping Icmm.i for context free languages. (10)
*b> Pcsign a IM>M"or lh language l.-Jwcw'' we (&,b ) (lOv
iVnk >hoif note >m loUovvmu iam iour):* <-0)
(a)Hjiltng pn'btcm
(bipost corresponding problem
(c)l'n\%TH4l rxi
\jnbtgucu* i*rammar (i i \htun-Ntf\k*
W KM'S NMiMS UNIVKKSITY MI KKSIIPVITI St H<>0| Ol l>VHNOl<x;Y MANAGKMKNT AN!) K.\GG.
It WxU I'nmramnu' (I'OMI*) 111 \ ear Irfm.Mrr V|| >> HI
Mihject: fhtHHTticjiK'oipulT Nd*mv Max. Marks: 10(1
IW Q$ . | O - QH n,,M* Allowed: J Hrs.
-f - p>'0
1) Uolu'i) N' I is oiui|tuKi i t |
umi* fumi thqn
1) <J
.*) Aik'nttx .m' ftmr lnm tttrtMnitining {(iii'Htttwy
I n) rV.Mjm iln l>l A I*>t tin- airing* in which IcOmoxt (10)
SmmK'I' thtlVi from vmK>f j jiivm (0, 1}.
ti*) IVsigii * IM wiiuif wiU Uv.>|jn.\ umUiiiingiiuniKrof*0h (10)
oittf 1 V I
i omiwiiw .uuUiWijM MtH< titJ \Uh iii.kIuiw. IKMgii j (10)
ni.n*hfrk* l. otnvcvt eteh iHwimcncv il Mthitfini* nhh hv nha. V {a, bf.
ftO Cmvii ihc MK*hhw iH.imnwr in (jhoimkv mmnU lonn, (10>
. S-MuU ;
A-frjAh . i
v > *
ir-fa) Ante .) pnj.uii u> uai\*UIc a kuUi c\imvsh>u to timtc <tuiomaU. (j(J)
-<b) .i NT \ (* the ivjttLir 0! * 1 itrul conwrt if fo 1)1* A. (jfjj
4. u) IVovc ihat if uinlccuUMc whclhci ,i omtcxt Irvc yunmuir is ambiguous. ()uj <H) IVsijm a It* .Kvvpitn? m Javh vvvi l#,W. (J
5. M) IX'sign J unit*! to. ompun lit (
ih) Fvpl.nn (M- *vh uniaMe example (|q
'* fa) State ml ptmr pumping I cinnu lm onu*\t Itvc Uniugcs (lj
Ml*) lVftign \*P l\i rttc l.wuagc \ - \\Svw1 : wr {a> |* J (
tVtitc sImmI nou-<hi MUmtug uin <**) (.\)
fnthtan
piohL m
TM
u()
Myhill-NuV" ilknflvni
B.Tech (C.Sc ) III Yr Trimester VU , 200S-2009
SyKM'1* NMIMS *fkl > ti
Subjrct: Theoretical Computer Science Date : 01/10/08
Marks:
Time :3brs lO DO - rOOftr* Isstruciions : Candidates should read carefully the instructions printed on the question paper and on the cover of the Answer Rook, which is provided for their use.
NB :
1. Question No. I is compulsory.
2. Out of remaining questions, attempt any four questions.
3. In all five questions to he attempted.
4. Answer to cach new question to be started on a fresh page.
5. Kiguru in brackets indicate full marks.
QI. a) t- if id R.I-. over V { 0, I }
i) Sel of all string* containing two cvnaccutivc 0 s.
iii Set of all strinas starting with ' I' and ending with "0 iiy .->1 ui all Dial s.Un aiiu end iUi Jilliu >h
iv) Set of ull strings that have 3fd symbol from last as * I'.
v) Sel of all strings that have exactly three 0s.
b) Find CK over {*bj (10)
i) Strings starting with 'a' and ending with 'b'.
ii) Strings starting and ending with different letter.
iii) Strings containing atteast two as.
iv) L - {{ ab* } U { a"b2*} 1 m,n> 1 }
v) L*(a,b,ckjj'! i+k, k > I)
Q2. a) Design Moore and Mealy machine to convert each occurance of (101
1000 to 1001 over = (0,1 }
h) Define CNF. Kxpicss the CFG in CNF (10)
S *> aSba | bSa | aa | a | b | bb
Q3 a) Construct PDA accepting (10)
I. |WfW* We|tb|*,WR Reverse ofW }
b) Us. ng Pumpmg lemroa prove that the given language is not regular. (10)
ii) L tn >s I |
|
Attachment: |
| Earning: Approval pending. |
