2007学年秋冬季学期

2006-2007《计算理论》课程期末考试开课学院：计算机学院考试形式：闭卷，允许带 考试时间:2007年1月24日，所需时间:120分钟，任课教师:考生 学号 专业题12345678总得ZhejiangTheoryofComputation,Fall-Winter2006FinalExam(30%)Determinewhetherthefollowingstatementsaretrueorfalse.IfitistruewriteaXotherwisea×inthebracketbeforethestatement. )IfaDFAMcontainsaself-looponsomestateq,thenMmustacceptaninfinitelanguage. )LetAandBbetworegularlanguages,soisA⊕B,whereA⊕B=(A−B)∪(B−A). ∪i=1 )Language{ucv|u,v∈{a,b}and|u|=2|v|}iscontext )SupposethatLisacontext-freelanguageandRisregular,L−Rcontext-free )Everycomputablefunctionisprimitive )Thecomplementofeveryrecursiveenumerablelanguageisrecursiveenu- )LetLbealanguageandthereisaTuringmachineMhaltsonxforx∈L,thenLis )Ifonecanlisttheelementsofalanguageinorder,thenthelanguagemustberecursive. )Languages{“M”:TuringmachineMacceptsatleast2007distinctinputs}isrecursiveenumerable.(12%)Decidewhetherthefollowinglanguagesareregularornotandprovideaformalproofforyouranswer.L1={aku|u∈{a,banducontainsatleastka’s,fork≥L2={aku|u∈{a,banducontainsatmostka’s,fork≥DescribethelanguageacceptedbythefollowingfiniteGiveaContext-freeGrammarforthe(14%)ConsiderthepushdownautomatonM={K,Σ,Γ,∆,s,F}whereK{s,f},Σ={a,b},Γ={b},F={f}and∆isgivenbythefollowing((p,a,β),(q,((s,a,e),(f,((s,b,e),(s,((s,a,b),(s,((s,e,e),(f,((f,a,e),(f,((f,b,e),(s,CanPDAMacceptstringDescribethelanguageacceptedbyMGiveaTuringmachinethatdecidesthesame(12%)Showthefollowing?f(x)

x+1, ifxisodd ifxisisprimitive(10%)ExplainthatwhythefollowingH={“M”:TuringmachineMhaltsonemptystringisrecursivelyenumerable.Aninformaldescription(10%)LetK0={“M”“w”:Mhaltsoninputstringw},K1={“M”:Mhaltsoninputstring“M”}.TrytosignlanguagesK0,K1andsetsoflanguagesrecursive,context-freelanguageandregulartothecorrespondingzoneofthefollowingfigure