課程名稱︰自動機與形式語言
課程性質︰必帶
課程教師︰項潔
開課學院：電機資訊學院
開課系所︰資訊工程學系
考試日期（年月日）︰2013/01/08
考試時限（分鐘）：180
是否需發放獎勵金：是
（如未明確表示，則不予發放）
試題 :
Formal Language and Automata Theory
Fall 2012 Final Exam
Tuesday, January 8, 2013
Total 180 minutes
Problem 1(15 points)
Prove that every infinite Turing-recognizable language has an infinite
decidable subset.
Problem 2(20 points)
Let A and B be two disjoint languages. Say that language C separates A and B
_
if A≦C and B≦C. Show that any two disjoint co-Turing-recognizable languages
are separable by some decidable language.
Problem 3(15 points)
Prove that there exists an undecidable subset of {1}*.
Problem 4(15 points)
There is a problem named 3-COLORING described as below:
3-COLORING={<G>|G is a graph and it can be colored by 3 or fewer colors such
that no adjacent nodes have the same color}.
(a) Prove that 3-COLORING is in NP.
(b) It is known that 3-COLORING is NP-complete. Show that 6-COLORING is also
NP-complete.
Problem 5(15 points)
Show that if P=NP, then for every language A in P, except ψ or Σ*, A is
NP-complete.
Problem 6(20 points)
Draw a table to indicate whether each of the class of P, NP, decidable, and
Turing-recognizable problems is closed under ∪, 。, ∩, ￣(complement).
For each of the negative answers, briefly explain why.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.244.207