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