计算理论复习

诚信考沉着应杜绝违浙江大学2008-2009秋冬学《计算理论》课程期末考试试开课学院：计算机学院考试形式：闭卷，允许带 入考试时间:2009年1月10日，所需时间:120分钟，任课教师: 诚信考沉着应杜绝违浙江大学2008-2009秋冬学《计算理论》课程期末考试试开课学院：计算机学院考试形式：闭卷，允许带 入考试时间:2009年1月10日，所需时间:120分钟，任课教师: 1234567题总得ZhejiangTheoryofComputation,Fall-Winter2008FinalExam(24%)Determinewhetherthefollowingstatementsaretrueorfalse.IfitistruewriteaTotherwiseaFinthebracketbeforethestatement.()ForalllanguagesL1andL2,ifL1iscontextfreeandL1⊆L2,thencannotbe((()ThereexistsalanguageLsuchthatLisnotregularbutL∗is)IfL1isregularandL2isnon-regular,thenL1◦L2mustbenon-)IfLisalanguageoveralphabetΣandthereisanintegerksuchthatstringw∈Lwith|w|>kcanbewrittenasw=uvxyzsuchthatfori≥0,vy=e,|vxy|≤kanduvixyiz∈L,thenLiscontext-(()Thecontext-freelanguagesareclosedunder)LetF={f:fisaprimitiverecursivefunctionfromNtoN},(PowersetofF)isuncountable(()Everycomputablefunctionisprimitive)TuringMachineswithktapescanacceptmorelanguagesthanMachineswithone )ThereexistsalanguageLsuchthatLisrecursivelyenumerableandLisnotrecursivelyenumerable.)ThereexistsalanguageLsuchthatLisrecursivelyenumerableandL()ThereisareductionfromAtoB,Aisrecursivelyenumerable,but(recursive,andBis()ThereareonlycountablymanyTuringmachines,andthereareablymanylanguages,somostlanguagesarenotTheoryofFinalExam(PageTheoryofFinalExam(Page2ofJan.10,(13%)LetΣ={a,bconsiderfollowinglanguage:L1={w:allsymbolsinΣmustappearinw}.Designafiniteautomatonthataccepts(b)Givearegularexpressionforthelanguage3.(14%)Decidewhetherthefollowinglanguagesareformalproofforyouranswer.(a)L2=mnm−n)mod36=regularornotandprovide(b)L3={w∈{a,∗w6=TheoryofFinalExam(Page3ofJan.10,(10%)TheoryofFinalExam(Page3ofJan.10,(10%)GiveContext-FreegrammarsthatgeneratethefollowingL4={w:w∈{a,bandwcontainstwomoreb0sthan0(15%)ConsiderthepushdownautomatonP={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,b,e),(s,CanPDAPacceptstringDescribethelanguageacceptedbyPGiveaTuringmachinethatdecidesthesameTheoryofFinalExam(Page4ofTheoryofFinalExam(Page4ofJan.10,(12%)LetthefollowingTuringmachineMcomputefunctionf(x,y),wherexyarerepresentedbybinarystringsrespectivelyandseparatedwiththesymboli.e.theinitialconfigurationinformof.x;y(a)DescribethekeyconfigurationswhenMstartedfromtheconfigurat