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

考試試卷：A B考試形式：閉 開卷，允許 考試日期:2012111日120誠信考試,沉著應(yīng)考, 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