課程名稱︰ 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/m.aspx?n=bbs/NTU-Exam/M.1421470048.A.FEE.html