若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={
证明：构造DFA N，使L(N)={含奇数个1的字符串}。构造图灵机
F=“对于输入
1) 构造DFA D，使L(D)=L(M)∩L(N)。 2) 检测L(D)是否为空。(EDFA可判定检测)。 3) 若L(D)＝?，则接受；否则拒绝。”
4.13 “检查一个CFG是否派生1*中某个串问题” 解： LX={
证明：构造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，则
5.2证明EQCFG是补图灵可识别的。
证明：注意到ACFG={
*
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图灵不可识别