计算理论导引习题答案[第2版]CHAP5new.docVIP

5.1 证明EQCFG是不可判定的。 解：只须证明ALLCFG≤mEQCFG 即可。 构造CFG G1，使L(G1)=∑*。设计从ALLCFG到EQCFG的归约函数如下： F=“对于输入＜G＞，其中G是CFG： 输出＜G,G1＞。” 若＜G＞(ALLCFG，则G,G1(EQCFG 。 若＜G＞(ALLCFG，则G, G1(EQCFG。 F将ALLCFG 归约到EQCFG 即ALLCFG≤mEQCFG ∵ALLCFG是不可判定的， ∴EQCFG是不可判定的。 5.2证明EQCFG是补图灵可识别的。 证明：注意到ACFG={G,w|G是能派生串w的CFG}是可判定的。构造如下TM： F=“输入G,H，其中G,H是CFG， 对于字符串S1, S2,(，重复如下步骤。 检测Si是否可以由G和H派生。 若G和H中有一个能派生w，而另一个不能，则接受。” F识别EQCFG的补。 5.3 略。 5.4 如果A(mB且B是正则语言，这是否蕴涵着A也是正则语言？为什么？ 解：否。例如： 对非正则语言A={0n1n|n(0}和正则语言B={0}，可以构造一个可计算函数f使得： f(w)= 于是w(A(f(w)(B,故A(mB。 5.5 证明ATM不可映射规约到ETM。 证明：反证法 假设ATM(mETM， 则有。而ATM的补不是图灵可识别的，从而可知ETM的补也不是图灵可识别的。 下面构造一个识别ETM的补的图灵机S： S=“输入M，M是TM, 对i=1,2,…重复下一步。 对S1,S2,…,Si模拟M运行i步，若有接受，则接受。” S可识别ETM的补，所以ETM的补是图灵可识别的，与上面由假设得到的ETM的补不是图灵可识别的矛盾。所以ATM不可映射规约到ETM。 5.6 略。 5.7证明：如果A是图灵可识别的，且A≤m，则A是可判定的。 证：∵A≤m≤mA 且A为图灵可识别的 ∴也为图灵可识别的 ∴由A和都是图灵可识别的可知A是可判定的. 5.8 解：在由M,w构造相应骨牌簇时，添加如下一类骨牌： 若M中有一个左移((q,a)=(r,b,L)，则添加一张骨牌： 。 并且第一张骨牌改为。 问题 5.x 证明所有的图灵可识别问题都映射可规约到ATM。 证明：设问题A是图灵可识别的，且M是识别A的TM。构造一个可计算函数f使得f(w)=M,w， 则有 w(A(f(w)( ATM。 这说明A≤m ATM。 5.9 证明S={M|M是TM且满足：只要它接受w，就接受wR}不可判定。 证明：对任意M,w，其中M是TM，w是串，令f(M,w)是如下TM： F=“输入x， 若x(01或10，则拒绝。 若x=01，则接受。 若x=10，则在w上运行M。若M接受，则接受。” 可以看到M,w(ATM( f(M,w)(S。ATM≤mS，所有S不可判定。 5.10 证明S={D,w|双带TM M在输入w上运行时会在第二条带上写下一个非空白符}是不可判定的。 证明：对任意M,w，其中M是单带确定TM，w是字符串。令f(M,w)=D,w，其中D是如下的双带TM： D=“输入x， 初始化，x放在第一带上，第二带为空。 在第一带上模拟M运行。 若M接受，则在第二带上写下一个非空白符，并接受；若M拒绝，则拒绝。” 从D的构造可以看出M,w(ATM(D,w(S，即ATM≤mS，所以S不可判定。 5.13 USELESSTM ={N| N是TM,并且N有无用状态}。 求 2) 输出N。” 对于任意TM M，如上构造的TM N，除接受状态外，每个状态均非无用状态(若在输入$上运行N，则N遍历q0,q1,q2,(,qn，最后进入qreject并停机)。构造N的目的就是消除M中任何非接受状态为无用状态的可能。因此有： M(ETM( N(USELESSTM M(ETM( N(USELESSTM 所以ETM≤mUSELESSTM而ETM不可判定，因此USELESSTM不可判定。 5.14 考虑这样的问题：检查图灵机在输入w上，当其读写头处于带最左方格时，是否曾经试图将读写头向左移。将这个问题形式化为一个语言，并证明它是不可判定的。 解：此问题可以形式化为一个语言S： S={M,w | TM M在输入w上，当其读写头处于带最左方格时，曾经试图将读写头向左移} 为证明S是不可判定的，可以证明ATM≤mS。构造一个可计算函数f:∑*(∑*,使得对每个M,w，其中M是TM，w是串，f(M,w)=M’,w，其中 M’=“输入x, 将工作带上内容改为$x。 读写头置于x的第一个字符，模拟M运行。 每当读写头移到$，保持状态，右移一格。 若M进入接受状态，读写头左移到$,再左移一次，停机，接受；若M进入拒绝状态，则拒绝。” 于是M,w(ATM(M’,w(S。 5.15