计算理论 试题答案（2007级）一、 证明：设M是一台识别语言B的DFA，交换M的接受状态与非接受状态得到一台新的DFA，则这台新DFA识别B的补集。因而，正则语言类在补运算下封闭。(8分)参考答案：设M是一台将DFAM的接受态与非接受态交换后的DFA，接下来证明M识别B语言，则M识别B的补集：假定M识别x，则对于x 在M上运行将结束于M的一个接受态，因为M和M交换了接受态与非接受态，因此对于x运行于M，将会结束于一个非接受态，所以x/B。类似地，如果x不被M接受，则它一定被M接受。故M恰好接受所有不被M接受的那些串，因此M识别B的补集。 既然B是任意的正则语言，且我们已构造出一台自动机识别它的补集，它表明任何正则语言的补也是正则的。因此，正则语言类在补运算下封闭。二、 令0，1，和ADDx=y+z | x，y，z是二制整数，且x是y与z的和，证明ADD不是正则的。(8分)参考答案：假定ADD是正则的。让P作为泵引理中的泵长度，选择S的串形式为1P0P1P作为ADD的一个成员。因为S有
