課程名稱︰自動機與形式語言
課程性質︰必修
課程教師︰項潔
開課學院：電資學院
開課系所︰資訊系
考試日期（年月日）︰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