=========================preview======================
(COMP272)1997_Quiz2Sol.pdf
Back to COMP272 Login to download
======================================================
COMP272TheoryofComputation
April30,1997,QuizTwo{Solutions

Name:M.J.Golin E-mail:[email protected]
.AnswerALLquestions.Forquestions1and2youareonlyrequiredtowritedowntheanswers. youdonotneedtojustifythem.Forquestion3youmustproveyouranswers.
.Timeallowed:50minutes.
.Theexamisworth150points.Eachquestionisworth50points.
1.RegularGrammars Let
.
L.fw2fa.bg:(Numberofa-sinwisoddandnumberofb-sisnotdivisibleby3)g
ConstructaregulargrammarGthatgeneratesL(i.e.,L(G).L).Recallthataregular
grammarisaspecialformofacontext-freegrammar. Solution:FirstbuildaDFAthatacceptsLandthentranslateitintoaregulargrammar thatgeneratesLbyusingtherulestaughtinclass.
b

S!bA S!aC
A!bB A!aD
B!bS B!aE
C!bD C!aS
D!bE D!aA
E!bC E!aB
D!e E!e
1

2.ContextFreeLanguagesandPushdownAutomata
(a)WritedownaContextFreeGrammarthatgeneratesthefollowinglanguage:
L.fa ibjc k:i.kori.jg
Note:theorisaninclusiveor,i.e.,allthreeofthefollowingpossibilitiesareallowed:(i) i.k.(ii)i.j,(iii)i.jandi.k. (b)BuildapushdownautomatonthatrecognizesL.Recallthatapushdownautomatonis oftheform M.(K...;...s.F)
where..thetransitionrelation,isoftheform
..(K....;.).(K.;.):
Inthiscase..fa.b.cgandyoumustspecifyalloftheremainingcomponentsofM:
(a)..fa.b.cg.V.fa.b.c.S.S1.S.B.Cgandtherulesare
2
S!S1CjS2. S1!ejaS1b.B!ejbB. C!ejcC.S2!BjaS2C
(b)SetK.fp.qg.;.fa.b.c.S.S1.S2.B.Cgs.p.andF.fqg: Thetransitionsare
((p.e.e).(q.S))
((q.e.S).(q.S1C))((q.e.S).(q.S2))
((q.e.S1).(q.e))((q.e.S1).(q.aS1b)) ((q.e.C).(q.e))((q.e.C).(q.cC)) ((q.e.B).(q.e))((q.e.B).(q.bB))
((q.e.S2).(q.B))((q.e.S2).(q.aS2c))
((q.a.a).(q.e))((q.b.b).(q.e)) ((q.c.c).(q.e))
2

3.Provingthatlanguagesare/arenotContextFree
(a)Thelanguage
L1.fa nbn c m:n.m.2ng

isnotContext-free.Provethisfact.Inyourprooffullystatethetheoremsthatyouare using(includingtheirassumptionsandtheirconsequences).
(b)Let
.
L2.fw2fa.b.cg:(Numberofa-sinw).(Numberofb-sinw)
and(Numberofa-sinw).(Numberofc-sinw).2.(Numberofa-sinw)g
IsL2Context-free.Proveyouranswer.Whenprovingyouranswer,fullystatethe theoremsthatyouareusing(includingtheirassumptionsandtheirconsequences).
(a)WeusethepumpingtheoremforCFLSwhichstatesthatifLisaCFLthenthereexists Ksuchthatforallw2Lwithjwj.K:thereexistu.v.x.y.zsuchthat (a)w.uvxyz (b)jvyj.1 (c)8s.0:uvsxysz2L
SupposethenthatL1isaCFL.LetKbetheconstantinthepumpingtheoremandde.ne KbKK
w.ac:Sincejwj.Kthereexistu.v.x.y.zsatisfying(a),(b)and(c).
Firstnotethatvcannotcontainmorethanonetypeofcharacterbecauseifitdid,e.g.,it containedaandb,thenuv2xy2zwouldcontainasubpatternoftheform...a...b...a...b whichisimpossiblesinceuv2xy2z2L1andstringsinL1cannotcontainthatsubpattern. Similarlyycannotcontainmorethanonetypeofcharacter.
Thusvycancontainatmosttwotypesofcharacters.
K+2K+2
Setw0.uvxyz.Wewillseethatregardlessofthechoiceofvandyitisalwaysthe casethat62L1:
w0
Firstsupposethatvycontainsonlyonetypeofcharacter,i.e.,onlya,onlyboronlyc:It cannotbeonlyabecausethenw0wouldcontainmorea-sthanb-sSimilarl