课程名称︰自动机与形式语言 课程性质︰必修 课程教师︰项洁 开课学院：电资学院 开课系所︰资讯工程学系 考试日期（年月日）︰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)