計(jì)算理論試卷ct g20062007學(xué)年秋冬季學(xué)期

2006-2007考試時(shí)間:2007年1月22日，所需時(shí)間:120分鐘，任課教師: 考生 12345678FinalExamitistruewriteaXotherwisea×inthebracketbeforethestatement. )Acountableunionofregularlanguagesisnecessarily )IfaDFAMcontainsaself-looponsomestateq,thenMmustacceptaninfinitelanguage. )Language{ucv|u,v∈{a,b?and|v|<|u|<2|v|}is )Foragivencontext-languageLandastringx,thedecisionproblemforwhetherx∈Lisdecidable. )Thecomplementofeveryrecursiveenumerablelanguageisnecessarilynonrecursiveenumerable. )Ifonecanlisttheelementsofalanguageinorder,thenthelanguagemustberecursive. )Languages{“M”:TuringmachineMacceptsmorethan2007distinctinputs}isrecursiveenumerable. )LetLbealanguageandthereisaTuringmachineMhaltsonxforx∈L,thenLis )IfLispolynomialtimereducibletoafinitelanguage,thenLisinP. )IfA≤pB,B≤pCandbothAandCareNP-complete,thenBNP-(12%)Decidewhetherthefollowinglanguagesareregularornotandprovideaformalproofforyouranswer.L={w∈{a,b?:|na(w)?nb(w)|mod2=FinalExam(PagePAGE2ofJan.22,L={w∈{a,b?:|na(w)?nb(w)|=wherena(w)andnb(w)givethenumberofaandbinwOnContext-(15%)ConsiderthepushdownautomatonM={K,Σ,Γ,?,s,F}whereK{s,f},Σ={a,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(11%)Showfunctionf(x,y)=x+f(x,y)=2x～y ifyis2isprimitive(10%)Showthatthecomputablefunctionsareclosedundercomposition,usingthedefinitionofcomputationoftheTuringmachine.Thatis,iffandgarecom-putablefunctions,showthatthefunction?givenby?(x)=f(g(x))isacomputableOn(12%)LetK0={“M”“w”:Mhaltsoninputstringw},K1={“M”:Mhaltsoninputstring“M”}.OntheassumptionthatP=NP,trytosignlanguagesK0,K1andsetsoflanguagesrecursive,P,NPandNP-Completetothecorrespondingzoneofthefollowingfigure:Note:r.e.isthesetofrecursiveenumerablelanguagesandCO-r.e.={L:comple-mentofLisr.e.}.OnPandNP(10%)TheSET-PACKINGproblemisdefinedasfollows:givenasetSwithnsetsandanumberk≤n,doesScontainskdisjointsets?ProvethatSET-PACKINGp