课程名称︰计算理论 课程性质︰选修 课程教师︰颜嗣钧 开课学院：电资学院 开课系所︰电机系 考试日期（年月日）︰2012/01/09 考试时限（分钟）：9:10 ~ 12:00 是否需发放奖励金：是 （如未明确表示，则不予发放） 试题 : Theory of Computtaion Final Exam,January 9, 2012 1.(20 pts) True or false? No explanations needed. Score＝max{0,Right－1/2 Wrong} (a) If L⊆0^* , then L is always recursive. (b) If L <=_m {0^n 1^n | n>= 0},then L is recursive. (c) {0^n 0^2n 0^3n |n >= 0} is context-free but not regular. (d) {xωx^R|x,ω∈{0,1}^+} is context-free but not regular. (e) {ωa^n a^n ω^R |ω∈{a,b}^* ,n>0} is context-free but not regular. (f) {a^n b^(n^2)|n >= 0} is not context-free. (g) u is a subsequence of v if u can be obtained by dropping symbols from u , where u,v ∈Σ^* . For example 11,011 are sequences of 1002.If A is context-free,then SUBSEQ(A) = {u | ∃u∈A such that u is a subsequence of v} is also context-free. (h) The language {< G > |G is context-free grammar and G is ambiguous} is recursively enumerable(r.e.). (i) The language {< M ,ω> | M is a linear bounded automaton and M accepts ω} is not recursive. (j) The language L = {< G,D > | G is a context-free grammar,D is a regular grammar} , and L(G)⊆L(D)} is recursive. 2. (20 pts) For the following languages , determine whether the language is (A) recursive , (B) recursively enumerable but not recursive, (C)not recursively enumerable. No explanations needed.No penalty for wrong answers. (a) L_1 = {< M > | M is a TM and there exists an input on which M halts in less than |< M >| steps} (b) L_2 = {< M > | M is a TM that accepts all even numbers}. (c) L_3 = {< M > | M is a TM and L(M) is finite}. (d) L_4 = {< M > |M is a TM and L(M) is infinite}. (e) L_5 = {< M > | M is a TM and L(M) is an uncountably infinite set}. (f) L_6 = {<M_1,M_2> |M_1,M_2 are TMs and ε∈L(M_1)∪L(M_2)}. (g) L_7 = {<M_1,M_2> | M_1,M_2 are TMs and ε∈L(M_1)∩L(M_2)}. (h) L_8 = {< M_1 ,M_2 >}M_1 , M_2 are TMs and ε∈L(M_1)－L(M_2)}. (i) L_9 = {< M > |M is a TM, and there exists an input whose length is less than 100 on which M halts} (j) L_10 = {< M >| M is a TM and M is the only TM that accepts L(M)} 3.(10 pts)Consider the following grammar: S → AB|BC A → AB|a B → CC|b C →BA|b Apply the CYK algorithm to determine whether the string ababa is generated by the grammar. Yoy need to draw the CYK table to show the computation. 4.(10 pts)For a language L⊆Σ^* , define reflect (L) = {ωω^R | ∃ω∈ L} where ω^R donotes the reverse of the string ω. (a) (4 pts) Consider L_0 = {0^i 1^i | i >= 0} and L_1 = 0^* 1^*. What are reflect (L_0) and reflect (L_1)? (b) (6 pts) Is the class of context-free languages closed under reflect ? Justify your answer. 5. (10 pts) Prove that the language L = {a^i b^j c^k |j<i , j<k} is NOT context-free. 6. (10 pts)For any language L⊆Σ^* , and any u∈Σ^* , let u/L = {v∈Σ^* | un∈L}. Prove that if L is context-free , then u/L is also contexr-free for every u∈Σ^*. (Hint: let u=a_1 ．．．a_k , for some k , and let M = (Q,Σ,Γ,δ,q_0,Z_0,F) be a PDA accepting L.Construct a PDA M' to accept u/L.) 7. (4 pts) Define context-sensitive grammars. 8.(10 pts) Let A , B ⊆ {0,1}^* be r.e. languages such that A∪B={0,1}^* and A∩B≠Φ. Prove that A <=_m (A∩B),where <=_m denotes the many-one reduction. (Hint: Let M_1 be a TM accepting A and M_2 be a TM accepting B. Further , since we know that A∩B ≠Φ , we know that some string y will be accepted by both M_1 and M_2. Construct a mapping f that witnesses <=_m, i.e., x∈ A ⇔ A∩B.) 9. - (6 pts) Suppose A is recursively enumerable and A<=_m A . Prove that A is recursive. --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.25.106