若M1接受所有段，则接受。”

M识别A*。所以图灵可识别语言类对星号运算是封闭的。 d．交

M= “对于输入w：

1) 在输入w上运行M1。若M1接受，则转(2)；若M1拒绝，则拒绝。 2) 在w上运行M2。若M2接受，则接受；若M2拒绝，则拒绝。” M识别A?B。所以图灵可识别语言类对并运算封闭。 3.21

1) 由cmax?|c1|知，当|x|?1，则欲判定不等式明显成立。 2) 当|x|>1时，由

c1xn + c2xn-1 + ?+ cnx + cn+1 = 0 ? c1x =－(c2 + ?+ cnx2-n + cn+1x1-n) ? |c1| |x| = |c2 + ?+ cnx2-n + cn+1x1-n|

< |c2| +?+ |cn||x|2-n + |cn+1| |x|1-n ? |c2| +??.|cn| + |cn+1||x0| ? n cmax

< (n + 1) cmax

? |x| < (n + 1) cmax / |c1|.

4.11 设A={|M是DFA，它不接受任何包含奇数个1的字符串}。证明A是可判定的。

证明：构造DFA N，使L(N)={含奇数个1的字符串}。构造图灵机

F=“对于输入，其中M是DFA，

1) 构造DFA D，使L(D)=L(M)∩L(N)。 2) 检测L(D)是否为空。(EDFA可判定检测)。 3) 若L(D)＝?，则接受；否则拒绝。”

4.13 “检查一个CFG是否派生1*中某个串问题” 解： LX={|G是{0，1}*上的CFG，且1*∩L(G)≠?}

证明：构造TM T

T＝“对于输入，A为CFG

1) 将终结符“1”和“?”做标记。

2) 重复下列步骤，直至无可做标记的变元。 3)

如G有规则A?U1U2?Un，且U1U2?Un中每个符号都已做过标记，则将A做标记，其中Ui为终结符或非终结符。

4) 如果起始变元没有被标记则拒绝，否则接受。” T判定LX。

5.7证明：如果A是图灵可识别的，且A≤mA，则A是可判定的。 证：∵A≤mA?A≤mA

且A为图灵可识别的 ∴A也为图灵可识别的

∴由A和A都是图灵可识别的可知A是可判定的. 5.1 证明EQCFG是不可判定的。 解：只须证明ALLCFG≤mEQCFG 即可。

构造CFG G1，使L(G1)=∑。设计从ALLCFG到EQCFG的归约函数如下：

F=“对于输入＜G＞，其中G是CFG： 1）输出＜G,G1＞。”

若＜G＞?ALLCFG，则?EQCFG 。 若＜G＞?ALLCFG，则?EQCFG。 F将ALLCFG 归约到EQCFG 即ALLCFG≤mEQCFG ∵ALLCFG是不可判定的， ∴EQCFG是不可判定的。

5.2证明EQCFG是补图灵可识别的。

证明：注意到ACFG={|G是能派生串w的CFG}是可判定的。构造如下TM： F=“输入，其中G,H是CFG，

*

1) 对于字符串S1, S2,?，重复如下步骤。 2) 3)

检测Si是否可以由G和H派生。

若G和H中有一个能派生w，而另一个不能，则接受。”

F识别EQCFG的补。

5.4 如果A?mB且B是正则语言，这是否蕴涵着A也是正则语言？为什么？ 解：否。例如：

对非正则语言A={0n1n|n?0}和正则语言B={0}，可以构造一个可计算函数f使得：

?0,w?0n1nf(w)=?nn?1,w?01

于是w?A?f(w)?B,故A?mB。

5.24证明：对任意字符串x，令f1(x)=0x。则有x?ATM?f1(x)=0x∈J。即有ATM≤m J。进一步有ATM?mJ。由ATM图灵不可识别知J图灵不可识别。 对任意字符串x，令f2(x)=1x。则有x?ATM?f2(x)=1x∈J。即有ATM?mJ。由ATM图灵不可识别知J图灵不可识别