课程名称︰自动机与形式语言 课程性质︰必修 课程教师︰项洁 开课学院：电资学院 开课系所︰资讯系 考试日期（年月日）︰100.01/11 考试时限（分钟）：190 (9:20~12:30) 是否需发放奖励金：是 （如未明确表示，则不予发放） 试题 : Threr are 7 problems and each of them is 15 points. Problem 1 Which of the following problems about Turing Machines are decidable, and which are undecidable? Explain your answers carefully. You will obtain no credit without a proof. ˙To determine, given a Turing machine M, an input string w, and a number k, whether M uses k tape squares on input w. ˙To determine, given a Turing machine M and a symbol a, whether M ever writes a when started with the empty tape. ˙To determine, given a Turing machine M, whether L(M) is finite. Problem 2 Show that a language L is decidable if and only if there is a Turing Machine M that enumerates elements of L in non-decreasing order. Prpblem 3 Show that the class of decidable languages is closed under the operations of ˙union, ˙concatenation, ˙Kleene star, ˙intersection, ˙complementation. Problem 4 Show that NP is closed under the Kleene star operation. Problem 5 Let f : N → N be any function where f(n) = o(n log n). Show that TIME(f(n)) contains only regular languages. Problem 6 Show the containment relationship among the following classes of languages: Turing-recognizable, co-Turing-recognizable, decidable, NP, coNP, P, context- free and regular. Note that you have to illustrate whether complexity class A is a proper subset of B. For example, P is a subset of NP but we don't know whether P is a proper subset of NP so far. Problem 7 Show that if P=NP, a polynomial time algorithm exists that takes an undirected graph as input and finds a largest clique contained in that graph. --

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