下载文档原格式
Graduate Course THEORY OF COMPUTATION College of Computer Science Final Exam Zhejiang UniversityFall2004Class：ID：Name：Score:Time allowed:2Hours.1.(20%)Determine whether the following statements are true or false.Ifit is true write a otherwise a×in the bracket before the statement.(a)()Every context-free language is recursive.(b)()Language{a m b n c l|m,n,l∈N,m+n>3l}is context free.(c)()All languages on an alphabet are recursively enumerable.(d)()There’s a language L such that L is undecidable,yet L and its complementare both semi-decided by the some Turing machine.(e)()There’s a functionϕsuch thatϕcan be computed by some Turing ma-chines,yetϕis not a primitive recursive function.(f)()Let L1,L2⊆Σ∗be languages,recursive functionτis a reduction from L1to L2,if L1is decidable,then so is L2.(g)()A language L is recursive if and only if it is Turing-enumerable.(h)()Every language in N P is recursive.(i)()Suppose A,B are two languages and there is a polynomial-time reductionsfrom A to B.If A is N P-complete,then B is N P-complete.(j)()Every language in N P-complete can be reducible to the3-SAT problem in polynomial time.2.(20%)F A and regular languages:(a)Decide whether the following language is regular or not and provide a formalproof for your answer.L={a m b n|m,n∈N,(m−n)mod3=0}(b)LetΣbe an alphabet and let L1,L2⊆Σ∗be languages so that L1is not regularbut L2is regular.Assume L1∩L2isfinite.Prove that L1∪L2is not regular.3.(20%)PDA and Context-free languages:(a)Give a context-free grammar for the languageL3={xy|x,y∈{a,b}∗,|x|=|y|and x and y R differ in one positions}.For example,abbbbaba,abbbbbbb∈L3,but aababb∈L3.(b)Design a PDA M=(K,Σ,Γ,∆,s,F)accepting the language L3.Solution:(b)The PDA M=(K,Σ,Γ,∆,s,F)is defined below:(q,σ,β)(p,γ)K=Σ={a,b}Γ=s=F=4.(10%)Numerical Functions:Let P(x,y)be primitive recursive predicates.Prove the following predicate∀y≤u P(x,y)is also primitive recursive.5.(10%)Turing MachinesDesign a Turing machine for computing the following function.f(x,y)=2x+1,if y is even4x,if y is oddwhere x and y are represented by binary strings respectively and separated with the symbol“;”,i.e.the initial configuration in form of x;y.6.(10%)Decidability and UndecidabilityShow that the following language{“M”“w”|M is a TM and M halts on w}is recursively enumerable.An informal description suffices.7.(10%)P and N P ProblemsGiven n natural numbers x1,x2,···,x n to test whether there exist distinct i1,i2,···,i ksuch that x i1+x i2+···+x ik=(x1+x2+···+x n)/2,and x i1+x i2+···+x ikis nota prime number.Design a N P algorithm for it,and estimate its time complexity.。
