计算理论复习

考试试卷：A B考试形式：闭 开卷，允许 考试日期:2012111日120诚信考试,沉着应考, 123456FinalExamitistruefilla⃝otherwisea×inthebracketbeforethestatement. )Language{xyz|x,y,z∈{a,b}∗,y=yR}isnot )LetAandBbetwolanguages.IfAisregularandBiscontextfree,A⊕Biscontextfree,whereA⊕B=(A−B)∪(B− )Language{ambnck|m,n,k∈Nandn̸=m+k}iscontext )Language{xcycz|x,y,z∈{a,b}∗and3|x|=2|z|}isnotcontext )JustasTuringMachine’sencoding,EveryPDAMcanalsobeencodedasstrings“M”,thenthelanguage{“M”|PDAMrejects“M”}isrecursive. ministicTuringMachines. )Language{“M”:TuringmachineMhaltsonatleastoneinput}isrecursivelyenumerable. )There’safunctionφsuchthatφcanbecomputedbysomeTuringma-chines,yetφisnotaprimitiverecursivefunction. )Language{“M”|MisaTuringmachine}isuncountable )ThereexistsalanguageLsuchthatbothLandLaresemi- )Language{“M”“w”|TuringmachineMhaltsoninputw}isrecursivelyenumerable,butnotrecursive. )Language{“M”|TuringmachineMhaltsonemptystring}isnotrecur-sivelyenumerable.(16%)L1={ambn|m,n∈Nandm≡ modGivearegularexpressionforthelanguageConstructafiniteautomatathataccepts(10%)ProvethatL2={amb2ncanb3m|m,n∈N}isnotregularbyapplyingthePumpingTheorem.(20%)LetL3={amb2ncanb3m|m,n∈Constructacontext-freegrammarthatgeneratesthelanguageConstructapushdownautomatathatacceptsSolution:(b)ThePDAM=(K,Σ,Γ,∆,s,F)isdefined((q,σ,(20%)LetthefollowingTuringmachineMcomputesafunctionf(x):N7→N,wherex∈Nisrepresentedbybinarystringwithoutredundantleading0’s,andtheinitialconfigurationinformof◃⊔x.GivetheconfigurationswhenMstartsfromtheinitialconfigurationTrytogivethefunctionf(x)computedbytheTMShowthatthefunctionf(x)isprimitive(10%)LetH1={“M”|Tu