計(jì)算理論復(fù)習(xí)

誠(chéng)信考沉著應(yīng)杜絕違浙江大學(xué)2008-2009秋冬學(xué)《計(jì)算理論》課程期末考試試開課學(xué)院：計(jì)算機(jī)學(xué)院考試形式：閉卷，允許帶 入考試時(shí)間:2009年1月10日，所需時(shí)間:120分鐘，任課教師: 誠(chéng)信考沉著應(yīng)杜絕違浙江大學(xué)2008-2009秋冬學(xué)《計(jì)算理論》課程期末考試試開課學(xué)院：計(jì)算機(jī)學(xué)院考試形式：閉卷，允許帶 入考試時(shí)間:2009年1月10日，所需時(shí)間: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