一.判断题
    1.任一空栈接收的PDA，存在一个终态接收的PDA与之等价。
    2.任一无二义性的CFG，存在一个DPDA接收该CFG生成的CFL。
    3.任意一个P问题都是NP的。
    4.任一递归可枚举语言(RE)，存在一个停机的TM接收它。
    5.在同一个字符集\Sigma下，空语言的Klein闭包不等于{\epsilon}的Klein闭包（即
\emptyset^{*} != {\epsilon}^{*}）。
    6.L1是正则语言，L2不是正则语言，则L1与L2的并不是正则语言。
    7.存在一个算法，判定两个正则表达式生成的语言是否相等。
    8.任一半无限长(semi-infinite)带的TM，存在一个双栈PDA与之等价。

二.单选，从A~H中选一个与1~6匹配
    1.L(a^{*}b^{*})
    2.{a^nb^n | n>0}
    3.{a^nb^m | n>m>0}
    4.{ww | w \in {a,b}^{*}}
    5.{ww^R | w \in {a,b}^{*}}
    6.L_u (i.e. {(M,w) | w \in L(M)})

    A.能被DFA接收 且 能被空栈接收的DPDA接收
    B.能被DFA接收 且 不能被任何空栈接收的DPDA接收
    C.能被终态接收或空栈接收的DPDA接收 且 不能被任何DFA接收
    D.能被终态接收的DPDA接收 且 不能被任何空栈接收的DPDA或DFA接收
    E.能被PDA接收 且 不能被任何DPDA接收
    F.能被停机的TM接收 且 不能被任何PDA接收
    G.能被TM接收 且 不能被任何停机的TM接收
    H.不能被任何TM接收

三.简答
    1. S -> AB
       A -> aAb | \epsilon
       B -> cB | \epsilon
    (1) 消去所有epsilon产生式
    (2) 在上一题的基础上消去所有unit产生式
    (3) 在上一题的基础上将文法转成CNF(Chormsky Normal Form)

    2. S -> DE | DC | CA | a
       A -> DE | DC
       B -> CA | DE | DC | a
       E -> BC
       C -> a
       D -> b
    (1) 在串baa上使用CYK算法，给出X_{ij} (1<=i<=j<=3)
    (2) 判断baa是否属于G[S]生成的语言

    3. S -> aSbS | aS | c
    (1) 说明G[S]是二义文法
    (2) 给出接收G[S]生成语言的空栈接收的PDA

    4. 给出判定如下问题的算法描述：
    (1) 给定CFG G，判断L(G)是否为空语言
    (2) 给定CFG G，判断\epsilon是否属于L(G)

    5. 给出了一个DFA A（原题用状态图给出）：
      ________|__a__|__b__|__
      -->*q_0 | q_1 | q_2 |
         *q_1 | q_1 | q_0 |
          q_2 | q_1 | q_2 |
    (1) 构造一个DFA 接收 ({a,b}^{*}-L(A))^R
    (2) 定义同态映射h: h(0)=ba, h(1)=ab，构造一个DFA 接收 h^{-1}(L(A))

    6. 给出 PDA P = (Q_p, \Sigma, \Gamma, \delta_p, q^p_0, Z_0, F_p)
         和 DFA D = (Q_d, \Sigma, \delta_d, q^d_0, F_d)
       设其分别接收语言L1，L2，要求构造一个PDA P^{'} 使其接收 L1交L2，给出P^{'}
的转移规则\delta即可
       （假设 P^{'} = (Q_p*Q_d, \Sigma, \Gamma, \delta, (q^p_0,q^d_0), Z_0,
F_p*F_d)，其中*为笛卡尔积）

四.构造题
    1. 构造一个DFA，要求|Q|<=8，使其接收语言
       L={w | w \in {0,1}^{*}, w包含00子串但不含000子串}

    2. 写出正则表达式E，要求运算符个数不超过8（括号不算），使其产生语言
       L={w | w \in {a,b}^{*}, w不含aa子串}

    3. 构造一个CFG，要求产生式数目不超过8，使其产生语言
       L={a^nb^mc^k | n<=m+k, n>=k, m,n,k>=0}

    4. 构造PDA，空栈接收或终态接收皆可，使其接收语言
       L={w | w \in {a,b,c}^{*}, w中a,b,c个数相等}

// 勘误：第四大题第4小题中，只能要求a,b个数相等……

    5. 构造TM，要求|Q|<=5，使其接收语言
       L={w | w \in {a,b}^{*}, w中a,b个数都是偶数}

五.证明题
    1. G[S]: S -> aSbb | aSbbb | \epsilon
       求证：L(G) = {a^nb^m | 2n<=m<=3n, n,m>=0}

    2. 证明 L={w | w \in {a,b,c,d}^{*}, w中a,b,c个数相等且a,b,c互不相邻} 不是CFL

    3. 证明子集构造算法的正确性