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?