推 asjh612 :符號補充: ⊆ ,⊂ ,∩是交集不是聯集 01/07 17:18
課程名稱︰自動機與形式語言
課程性質︰必修
課程教師︰項潔
開課學院：電資學院
開課系所︰資訊工程學系
考試日期（年月日）︰2014/1/7
考試時限（分鐘）：180
是否需發放獎勵金：yes :)
（如未明確表示，則不予發放）
試題 :
Final exam CSIE3110 7 January, 2014
1. (15 pts) Let A = { < R, S > | R and S are regular expressions and
L(R)≦ L(S)}. Show that A is decidable.
↑
包含於的意思
2. (15 pts) Let FINITESTEP_TM = { <M> | M is a TM that accepts some input in
1024 steps}. Is FINITESTEP_TM decidable? Justify your answer.
3.
3.1 (10 pts) Show that if an enumerator E prints its outputs in a
non-decreasing fashion (the length of every output string is at least
as long as the previous one), then L(E) is decidable.
3.2 (10 pts) Use 3.1 to show that every infinite Turing-recognizable set
has an infinite decidable subset.
4. (15 pts) Show that if there is an L ＜ NP ︿ coNP and L is also NP-complete,
↑ ↑
包含於 聯集
then NP = coNP
5. (30pts) A k-PDA is a PDA with k stacks.
5.1 Define a k-PDA formally.
5.2 Show that every Turing Machine can be simulated by a 2-PDA.
5.3 Show that 3-PDAs are no more powerful than 2-PDAs.
6. (15 pts) Use the Diagonalization Principle to show that the set of infinite
strings over {0,1} is uncountable.
※ 編輯: yet5438 來自: 140.112.16.137 (01/07 15:11)