参考文稿成果

2009-2010《计算理论》课程期末考试课程号 开课学院：计算机学考试试卷：A考试形式：闭卷，允许 入考试日期:2010128日120诚信考试,沉着应考,杜考生学 所属院题1234567总得评卷ZhejiangTheoryofComputation,Fall-Winter2009FinalExam(24%)Determinewhetherthefollowingstatementsaretrueorfalse.IfitistruefillaTotherwiseaFinthebracketbeforethestatement. )ForlanguagesL1andL2,ifL1isnon-regularandL1⊆L2,thenL2is )IfL1andL2arebothnon-regular,thenL1∪L2couldbe )ThereexistsalanguageLwithe6∈LsuchthatL+=L∗,whereL+= )JustasTuringMachine’sencoding,DFAsMcanalsobeencodedas“M”,thenlanguage{“M”|“M”6∈L(M)}is )JustasTuringMachine’sencoding,DFAsMcanalsobeencodedasstrings“M”,thenlanguage{“M”|“M”6∈L(M)}isdecidable. )Languagevv∈{a,∗|u|≤|v|≤2|u|}iscontext- )LetB=mmm|∈N}andA≤τB,whererecursivefunctionτisreductionfromAtoB,thenAisG )LetGbeaCFG,ifS⇒∗w,thenthereexistsaleftmostG⇒G )Everycontext-freelanguageisrecursively )Alllanguagesonalphabet{a}canbesemi-decidedbyaTuring )IfbothlanguageLanditscomplementarerecursivelyenumerable,Lis )TherecursivelyenumerablelanguagesareclosedunderSolution:(a)F(b)F(c)F(d)F(e)T(f)T(g)T(h)T(i)T(j)F(k)T(l)(14%)OnFiniteConsiderthefollowingNFAMon{a,lwhatlanguagethatNFAMDescribethekeyideaofconstructionanequivalentDFAfromaConstructanequivalentDFAfromtheNFAMNFAMacceptsthelanguageL=∗b(b∪ba∗b)=a∗{, 6

L={w∈{a,b∗|containsatleastoneDescribethekeyideaofconstructionanequivalentDFAfromaNFA:EverysubsetofK esasinglestateinournewmachine!·········· 4ptsConstructanequivalentDFAfromtheNFAMForeveryqi(i=1,2),wecanobtainE(q1)={q1},E(q2)= Accordingtodefinitionofδ(Q,a)=∪{E(p)|p∈Kand(q,a,p)∈∆forsomeq∈Q},foreachQ⊆Kand∀a∈{a,bwecanobtain:δ({q1},a)={q1},δ({q1},b)={q2},δ({q2},a)={q2},δ({q2},b)={q1,δ({q1,q2},a)={q1,q2},δ({q1,q2},b)= 2(12%)OnRegularShowthattheL1={w∈{a,b∗|hasunequalnumbersof0and0isnot1Solution:AssumeL1isregular,byclosureproperties,wekonow0={w1{a,b∗|hasequalnumbersof0and0isalsoregular.·········· 4ptsButL1isnotregular,wecanusepum theoremtoproveit.AssumeL0isregular,letnbetheconstantwhoseexistencethepum Choosestringw=2n2∈L0,wheren∈N.········· 4ptsSothepumtheoremmusthold.Letw=xyzsuchthat|xy|≤nandy6=e,theny=aiwherei>0.Butxz=2−i26∈L1. 4Thetheoremfails,thereforeL1isnotregular,henceL1isalsonotregular(16%)OnContext-freeConstructacontext-freegrammarthatgeneratestheL2=mbn|m,n,k∈N,andn≥m+ConstructapushdownautomatathatacceptsWecanconstructthecontext-freegrammarG=(V,Σ,R,S)forlanguageL2,whereV={a,b,c,S1,S2,S3};Σ={a,b,c};and 4ptsR={S→S1S2S3,S1→aS1b,S2→bS2,S3→bS3c,S1→e,S2→e,S3→e, 4ThePDAM=(K,Σ,Γ,∆,s,F)isdefined(q,S1S2S3;Γ= } 8(12%)OnTuringDesignasingletapeTuringmachineMthatdecidesthelanguageL3on{a,bL3=nbn|∈N,n≥WhendescribingtheTuringmachinesabove,youcanusetheelementaryTuringmachinesdescribedintextbook.AlwaysassumethatyourTuringmachinestartstheconfigurationw 12(10%)OnPrimitiveRecursiveShowthatthepredicatecomposite(x)(xisacompositenumber)isprimitiverecur-composite(x)⇔1∼⇔(x>1)∧x)6=1∧ 10(12%)OnClassifywhethereachofthefollowinglanguagesarerecursive,recursivelyenumerable-but-not-recursive,ornon-recursivelyenumerable.Proveyouranswers.L4={“M”|TuringmachineMhaltson“ML5={“M”|TuringmachineMdoesnothalton“ML4isrecursivelyenumerable-but-not-First,WecanuseU(UniversalTuringmachine)tosimulateTuringMon“M”,IfUniversalTuringmachineUhaltson“M”,then“yes”,otherwiseUcheckthehaltingcomputationofMon“M”.Hence,L4isrecursivelyenumerable.·6Secondly,wewillshowthatL4isnotrecursive.Wecanestablishaτ:{“M”|Mhaltsone}toL4.Thereductionτ(“M”)=“M”“M·3L5isnon-recursivelyenumerable.SupposethatL5isrecursivelyenu-merable,thereexistsaTuringmachineM∗semidecidesL5.Is“M∗”∈L5?AccordingtothedefinitionofL5,“M∗”∈L5ifandonlyifM∗doesnothalton“M∗”.ButM∗issupposedtosemidecidesL5,so“M∗