課程名稱︰ 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.