课程名称︰ 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.