计算理论复习

课程号 考试形式：闭 开卷，允许 考试日期:2013118日120诚信考试,沉着应考, 123456FinalExamitistruefilla⃝otherwisea×inthebracketbeforethestatement. )Language{xyz|x,y,z∈{a,b}∗andx=zRand|x|≥1}is )LetAandBbetworegularlanguages,thenA⊕Bisalsoregular,A⊕B=(A−B)∪(B− )JustasTuringMachine’sencoding,everyDFAMcanalsobeencodedasstrings“M”,thenthelanguage{“M”|DFAMrejects“M”}isregular. )Language{ambnckdl|m,n,k,l∈N,m≥landn≤k}isnotcontext )ForlanguagesL1,L2andL3,ifL1⊆L2⊆L3andbothL1andL3arecontextfree,thenL2isalsocontextfree. )Foranyk>1,k-tapesTuringMachinescandecidemorelanguagesthan1-tapeTuringMachines. )Language{“M”|TuringmachineMhaltsonatleast2013inputs}isrecursivelyenumerable,butnotrecursive. )Thesetofallprimitiverecursivefunctionsisapropersubsetofthesetofallrecursivefunctions. )ThereexistsalanguageLsuchthatLisrecursivelyenumerable,andLis )Language{“M”|TuringmachineMdoesnothalton“M”}isrecursively )Therecursivelyenumerablelanguagesareclosedunderintersection,butnotclosedundercomplement. )TherearecountablymanyTuringmachines,anduncountablymanylan-guages,somostlanguagesarenotrecursivelyenumerable.(20%)Decidewhetherthefollowinglanguagesareregularornotandprovideaformalproofforyouranswer.L1={ambnck|m,n,k∈Nandm̸=n+kL2={ambnck|m,n,k∈Nand(m̸≡(n+k))mod2(20%)LetΣ={a,b,c}.LetL3={w|w∈{a,b,c}∗,#b(w)=#c(w)}.Wherex=baccabcbcb∈L3,since#b(x)=#c(x)=4.Similarly,thestringx=abcabaL3,since#b(x)=2and#c(x)=Solution:(b)ThePDAM=(K,Σ,Γ,∆,s,F)isdefined (p,γ(20%)Thefunctionφ:N→Ngiven{ ifx<φ(x)

4x+ ifx≥theconfiguration◃⊔xwherexisrepresentedbybinarystring,i.e.x∈{0,1}∗.Showthatthefunctionφ(x)isprimi