《计算理论导引习题答案[第2版]第5章》由会员分享，可在线阅读，更多相关《计算理论导引习题答案[第2版]第5章（6页珍藏版）》请在金锄头文库上搜索。
1、5.1 证明EQCFG是不可判定的。解：只须证明ALLCFGmEQCFG 即可。构造CFG G1，使L(G1)=*。设计从ALLCFG到EQCFG的归约函数如下：F=“对于输入G，其中G是CFG：1） 输出G,G1。”若GALLCFG，则EQCFG 。若GALLCFG，则EQCFG。F将ALLCFG 归约到EQCFG 即ALLCFGmEQCFGALLCFG是不可判定的，EQCFG是不可判定的。5.2证明EQCFG是补图灵可识别的。证明：注意到ACFG=|G是能派生串w的CFG是可判定的。构造如下TM：F=“输入，其中G,H是CFG，1) 对于字符串S1, S2,，重复如下步骤。2) 检测Si是
2、否可以由G和H派生。3) 若G和H中有一个能派生w，而另一个不能，则接受。”F识别EQCFG的补。5.3 略。5.4 如果AmB且B是正则语言，这是否蕴涵着A也是正则语言？为什么？解：否。例如：对非正则语言A=0n1n|n0和正则语言B=0，可以构造一个可计算函数f使得：f(w)= 于是wAf(w)B,故AmB。5.5 证明ATM不可映射规约到ETM。证明：反证法假设ATMmETM， 则有。而ATM的补不是图灵可识别的，从而可知ETM的补也不是图灵可识别的。下面构造一个识别ETM的补的图灵机S：S=“输入，M是TM,1) 对i=1,2,重复下一步。2) 对S1,S2,Si模拟M运行i步，若有接
3、受，则接受。”S可识别ETM的补，所以ETM的补是图灵可识别的，与上面由假设得到的ETM的补不是图灵可识别的矛盾。所以ATM不可映射规约到ETM。5.6 略。5.7证明：如果A是图灵可识别的，且Am，则A是可判定的。证：AmmA且A为图灵可识别的也为图灵可识别的由A和都是图灵可识别的可知A是可判定的.5.8 解：在由构造相应骨牌簇时，添加如下一类骨牌：若M中有一个左移d(q,a)=(r,b,L)，则添加一张骨牌：。并且第一张骨牌改为。问题5.x 证明所有的图灵可识别问题都映射可规约到ATM。证明：设问题A是图灵可识别的，且M是识别A的TM。构造一个可计算函数f使得f(w)=， 则有wAf(w)
4、 ATM。 这说明Am ATM。5.9 证明S=|M是TM且满足：只要它接受w，就接受wR不可判定。证明：对任意，其中M是TM，w是串，令f()是如下TM：F=“输入x，1) 若x01或10，则拒绝。2) 若x=01，则接受。3) 若x=10，则在w上运行M。若M接受，则接受。”可以看到ATM f()S。ATMmS，所有S不可判定。5.10 证明S=|双带TM M在输入w上运行时会在第二条带上写下一个非空白符是不可判定的。证明：对任意，其中M是单带确定TM，w是字符串。令f()=，其中D是如下的双带TM：D=“输入x，1) 初始化，x放在第一带上，第二带为空。2) 在第一带上模拟M运行。3)
5、若M接受，则在第二带上写下一个非空白符，并接受；若M拒绝，则拒绝。”从D的构造可以看出ATMS，即ATMmS，所以S不可判定。5.13 USELESSTM =| N是TM,并且N有无用状态。 求证USELESSTM不可判定。证明：构造ETM到USELESSTM的规约函数:F=“对于输入,M=(Q,S,G,d,q0,qaccept,qreject)是TM,1) 构造TM NN=(Q,S1,G1,d1,q0,qaccept,qreject)，其中，S1=S$,G1=G1$。设Q=q0,q1,q2,qn,qreject ,qaccept 。对任意qQ，aG1：2)输出。”对于任意TM M，如上构造的
6、TM N，除接受状态外，每个状态均非无用状态(若在输入$上运行N，则N遍历q0,q1,q2,qn，最后进入qreject并停机)。构造N的目的就是消除M中任何非接受状态为无用状态的可能。因此有：ETM USELESSTMETM USELESSTM所以ETMmUSELESSTM而ETM不可判定，因此USELESSTM不可判定。5.14 考虑这样的问题：检查图灵机在输入w上，当其读写头处于带最左方格时，是否曾经试图将读写头向左移。将这个问题形式化为一个语言，并证明它是不可判定的。解：此问题可以形式化为一个语言S： S= | TM M在输入w上，当其读写头处于带最左方格时，曾经试图将读写头向左移为证
7、明S是不可判定的，可以证明ATMmS。构造一个可计算函数f:*,使得对每个，其中M是TM，w是串，f()=，其中M=“输入x,1) 将工作带上内容改为$x。2) 读写头置于x的第一个字符，模拟M运行。3) 每当读写头移到$，保持状态，右移一格。4) 若M进入接受状态，读写头左移到$,再左移一次，停机，接受；若M进入拒绝状态，则拒绝。”于是ATMS。5.15 证明S=|图灵机M在输入w上运行时有左移可判定。证明：构造如下TM F：F=“输入，M是TM，w是串，1) 计算M的状态数，记为p。2) 在w上模拟M，直到有左移，或停机，或已运行了|w|+p步。3) 若有左移，则接受；若停机但无左移，则拒
8、绝；若无左移且不停机，则拒绝。”需要说明的是在|w|+p步运行中无左移也不停机的情况。由于无左移，M运行|w|步以后进入空白区域。由于此后右移使得每次读写头所指向的都是空格，而且此后运行的p步至少会有一个状态出现两次，所以不停机意味着M进入了循环，也就不会出现左移。总之，F判定S。5.17 证明PCP在一元字母表上,即在字母表=1上,是可判定的.证明：构造识别该语言的图灵机如下:S=“对输入的骨牌序列,扫描骨牌序列。若所有的骨牌的上面的1的个数都大于下面的1的个数，或都小于下面的1的个数，则拒绝。否则，接受。”S判定这样的PCP。5.18证明PCP在二元字母表上，即在字母表=0，1上，是不可判
9、定的。证明：要想证明该PCP(记为PCP2)是不可判定的，只须证明ATMmPCP2。为此需要利用定理5.11的证明过程和规约的传递性：首先，把书中的PCP任一实例P映射到PCP2的实例P2设计从P到P2的规约函数如下：F=“对输入，其中P是PCP：1) 造 PCP P2，对P中所有骨牌中包含的字符串进行Huffman编码，形成一一对应的只含0和1的字符串(也可进行定长编码)。2) 输出。”F将PCP映射规约到PCP2，即PCPmPCP2；其次，有定理5.11有ATMmPCP；根据规约的传递性可知，ATMmPCP2ATM是不可判定的，PCP2是不可判定的。5.21 设AMBIGCFG|G是歧义的
10、CFG。证明AMBIGCFG是不可判定的。证明：设AMBIGCFG是可判定的，且R判定AMBIGCFG构造S判定PCPS“对于任一PCP输入，如pt1/b1,t2/b2,.,tk/bk1)利用如下规则构造一个CFG G：ST|BTt1Ta1|t2Ta2|.|tkTak|t1a1|.|tkakBb1Ba1|b2Ba2|.|bkBak|t1a1|.|bkak2)在上运行R，如果R接受则接受，如果R拒绝则拒绝。”其中ai保证在Tt1Ta1|t2Ta2|.|tkTak|t1a1|.|tkak不是歧义CFG。这样，如果AMBIGCFG是可判定的，则有PCP可判定的，而PCP是不可判定的，导出矛盾。所以可
11、以得到AMBIGCFG是不可判定的。5.x 证明：举反例：令A=|M是图灵机。则A满足问题xxx中的条件a,不满足条件b。但是A是可判定的，只要证明是否符合图灵机的形式定义即可。因此，只满足条件a,不满足条件b不能导出不可判定。令B=M1,其中M1是一台图灵机。则B满足问题xxx中的条件b,不满足条件a。但是B是可判定的。因此，只满足条件b,不满足条件a不能导出不可判定。5.24证明：对任意字符串x，令f1(x)=0x。则有xATMf1(x)=0xJ。即有ATMm J。进一步有m。由图灵不可识别知图灵不可识别。对任意字符串x，令f2(x)=1x。则有xATMf2(x)=1xJ。即有mJ。由图灵
12、不可识别知J图灵不可识别。5.25给出一个不可判定语言B的例子，使得Bm。解：可利用第10题的结果。令B为5.24中的J，则Jm。构造归约函数如下F=“输入w，1） 对w的第一位取反，即0变1，1变0。2） 输出w。”则F把J映射归约到。而J 又是不可判定的。5.26证明：(a)判定A2DFA的算法如下：L=“对于输入，其中M是2DFA，x是串，1) 计算M的状态个数q，和x的长度n。2) 在x上模拟M qn2步，或直至它停机；3) 若M停机，则当M接受时接受，拒绝时拒绝。若未停机，则拒绝。”因为M有q个状态，所以对长度为n的输入，M至多有qn2个不同格局(注意：带上的内容不会改变)。若模拟q
13、n2步还未停机，则必定是进入了循环，该情况下应拒绝。(b) 构造从ATM到E2DFA的补的映射归约函数。对于任意给定的，f()=是如下的2DFA的描述：B=“输入x,若x=#C1#C2#Cm# 是，即检查x满足：a) C1是M在上的起始格局。b) 每个Ci+1都是Ci的合法结果。c) Cm是M的一个接受格局。则接受。”条件a,c较容易验证。验证b时，B的两个读头分别在Ci和Ci+1的相应位置上移动，验证结果是否适当。由B的构造可以看到ATM f()=E2DFA此即ATM映射可归约到E2DFA的补。由ATM不可判定，知E2DFA不可判定。5.27 证明EQ2DIM-DFA不可判定。证明：下面证明ATM映射可归约到EQ2DIM-DFA的补：对于任意，f()=是如下的两个2DIM-DFA的描述，其中H满足L(H)=。为构造G，记格局序列C1,C2,Cm的编码为，它是由格局序列C1,C2,Cm组成的矩形串。其由下至上分别是C1,C2,Cm，一个格局一行，较短的在右边补上适当数量的空格，四周是由#围成的方框。G=“输入串x，若x=是，即x满足：a) C1是M在w上的起始格局。b) 每个Ci+1都是Ci的合法结果。c) Cm是M的一个接受格局。则接受。”由G,H的构造可以看到ATM f()=EQ2DIM-DFA此即ATM映射可归约到EQ2
