课程名称︰ Formal Languages and Automata Theory 课程性质︰ 必 修 课程教师︰ 项 洁 开课学院： 资讯电机学院 开课系所︰ 资讯系 考试日期（年月日）︰ 12 Jan, 2015 考试时限（分钟）： 试题 : 1. (20pts) Define a PDA (pushdown automata) with 2 stacks. Explain why such a device is equivalent to Turing machines. 2. (15pts) Consider the problem of testing whether a DFA and a regular expression are equivalent. Express the problem as a language and show that it is decidable. 3. (15pts) Show that a languahe L is decidable if and only if there is a Turing Machine M that enumerates elements of L in non-decreasing order. (assuming a partial order on the elements of sigma*) 4. (15pts) A language is co-NP if its complement is NP. The class coNP is the set of languages that are co-NP. Show that if NP =/= co-NP, then P =/= NP. 5. (20pts) Draw a table to indicate whether each of the class of P, NP, decidable, and Turing-recognizable problems are closed under union, concatation, intersection, complement. 6. (15pts) Show that there exist some undecidable language L that is mapping reducible to its complement, i.e. L <=m Lbar. --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 118.165.192.164 ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/NTU-Exam/M.1421470048.A.FEE.html