计算理论导引习题答案[第2版]第5章

5.1证明EQCFG是不可判定的。解：只须证明ALLCFG≤mEQCFG即可。构造CFGG1，使L(G1)=∑*。设计从ALLCFG到EQCFG的归约函数如下：F=“对于输入＜G＞，其中G是CFG：1）输出＜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，1)对于字符串S1,S2,，重复如下步骤。2)检测Si是否可以由G和H派生。3)若G和H中有一个能派生w，而另一个不能，则接受。”F识别EQCFG的补。5.3略。5.4如果AmB且B是正则语言，这是否蕴涵着A也是正则语言？为什么？解：否。例如：对非正则语言A={0n1n|n0}和正则语言B={0}，可以构造一个可计算函数f使得：f(w)=nnnn10w1,10w0,于是wAf(w)B,故AmB。5.5证明ATM不可映射规约到ETM。证明：反证法假设ATMmETM，则有TMmTMEA。而ATM的补不是图灵可识别的，从而可知ETM的补也不是图灵可识别的。下面构造一个识别ETM的补的图灵机S：S=“输入M，M是TM,1)对i=1,2,…重复下一步。2)对S1,S2,…,Si模拟M运行i步，若有接受，则接受。”S可识别ETM的补，所以ETM的补是图灵可识别的，与上面由假设得到的ETM的补不是图灵可识别的矛盾。所以ATM不可映射规约到ETM。5.6略。5.7证明：如果A是图灵可识别的，且A≤mA，则A是可判定的。证：∵A≤mAA≤mA且A为图灵可识别的∴A也为图灵可识别的∴由A和A都是图灵可识别的可知A是可判定的.5.8解：在由M,w构造相应骨牌簇时，添加如下一类骨牌：若M中有一个左移(q,a)=(r,b,L)，则添加一张骨牌：rbqa##。并且第一张骨牌改为wq0###。问题5.x证明所有的图灵可识别问题都映射可规约到ATM。证明：设问题A是图灵可识别的，且M是识别A的TM。构造一个可计算函数f使得f(w)=M,w，则有wAf(w)ATM。这说明A≤mATM。5.9证明S={M|M是TM且满足：只要它接受w，就接受wR}不可判定。证明：对任意M,w，其中M是TM，w是串，令f(M,w)是如下TM：F=“输入x，1)若x01或10，则拒绝。2)若x=01，则接受。3)若x=10，则在w上运行M。若M接受，则接受。”可以看到M,wATMf(M,w)S。ATM≤mS，所有S不可判定。5.10证明S={D,w|双带TMM在输入w上运行时会在第二条带上写下一个非空白符}是不可判定的。证明：对任意M,w，其中M是单带确定TM，w是字符串。令f(M,w)=D,w，其中D是如下的双带TM：D=“输入x，1)初始化，x放在第一带上，第二带为空。2)在第一带上模拟M运行。3)若M接受，则在第二带上写下一个非空白符，并接受；若M拒绝，则拒绝。”从D的构造可以看出M,wATMD,wS，即ATM≤mS，所以S不可判定。5.13USELESSTM={N|N是TM,并且N有无用状态}。求证USELESSTM不可判定。证明：构造ETM到USELESSTM的规约函数:F=“对于输入M,M=(Q,,,,q0,qaccept,qreject)是TM,1)构造TMNN=(Q,1,1,1,q0,qaccept,qreject)，其中，1={$},1=1{$}。设Q={q0,q1,q2,,qn,qreject,qaccept}。对任意qQ，a1：.$,),,$,(,0,$,),,$,($,),,(),(11nrejectiiqqaLqniqqaLqaaqaq2)输出N。”对于任意TMM，如上构造的TMN，除接受状态外，每个状态均非无用状态(若在输入$上运行N，则N遍历q0,q1,q2,,qn，最后进入qreject并停机)。构造N的目的就是消除M中任何非接受状态为无用状态的可能。因此有：METMNUSELESSTMMETMNUSELESSTM所以ETM≤mUSELESSTM而ETM不可判定，因此USELESSTM不可判定。5.14考虑这样的问题：检查图灵机在输入w上，当其读写头处于带最左方格时，是否曾经试图将读写头向左移。将这个问题形式化为一个语言，并证明它是不可判定的。解：此问题可以形式化为一个语言S：S={M,w|TMM在输入w上，当其读写头处于带最左方格时，曾经试图将读写头向左移}为证明S是不可判定的，可以证明ATM≤mS。构造一个可计算函数f:∑*∑*,使得对每个M,w，其中M是TM，w是串，f(M,w)=M’,w，其中M’=“输入x,1)将工作带上内容改为$x。2)读写头置于x的第一个字符，模拟M运行。3)每当读写头移到$，保持状态，右移一格。4)若M进入接受状态，读写头左移到$,再左移一次，停机，接受；若M进入拒绝状态，则拒绝。”于是M,wATMM’,wS。5.15证明S={M,w|图灵机M在输入w上运行时有左移}可判定。证明：构造如下TMF：F=“输入M,w，M是TM，w是串，1)计算M的状态数，记为p。2)在w上模拟M，直到有左移，或停机，或已运行了|w|+p步。3)若有左移，则接受；若停机但无左移，则拒绝；若无左移且不停机，则拒绝。”需要说明的是在|w|+p步运行中无左移也不停机的情况。由于无左移，M运行|w|步以后进入空白区域。由于此后右移使得每次读写头所指向的都是空格，而且此后运行的p步至少会有一个状态出现两次，所以不停机意味着M进入了循环，也就不会出现左移。总之，F判定S。5.17证明PCP在一元字母表上,即在字母表∑={1}上,是可判定的.证明：构造识别该语言的图灵机如下:S=“对输入的骨牌序列P,扫描骨牌序列。若所有的骨牌的上面的1的个数都大于下面的1的个数，或都小于下面的1的个数，则拒绝。否则，接受。”S判定这样的PCP。5.18证明PCP在二元字母表上，即在字母表Σ={0，1}上，是不可判定的。证明：要想证明该PCP(记为PCP2)是不可判定的，只须证明ATM≤mPCP2。为此需要利用定理5.11的证明过程和规约的传递性：首先，把书中的PCP任一实例P映射到PCP2的实例P2设计从P到P2的规约函数如下：F=“对输入P，其中P是PCP：1)造PCPP2，对P中所有骨牌中包含的字符串进行Huffman编码，形成一一对应的只含0和1的字符串(也可进行定长编码)。2)输出P2。”F将PCP映射规约到PCP2，即PCP≤mPCP2；其次，有定理5.11有ATM≤mPCP；根据规约的传递性可知，ATM≤mPCP2∵ATM是不可判定的，∴PCP2是不可判定的。5.21设AMBIGCFG＝{G|G是歧义的CFG}。证明AMBIGCFG是不可判定的。证明：设AMBIGCFG是可判定的，且R判定AMBIGCFG构造S判定PCPS＝“对于任一PCP输入，如p＝{[t1/b1],[t2/b2],...,[tk/bk]}1)利用如下规则构造一个CFGG：ST|BTt1Ta1|t2Ta2|...|tkTak|t1a1|...|tkakBb1Ba1|b2Ba2|...|bkBak|t1a1|...|bkak2)在G上运行R，如果R接受则接受，如果R拒绝则拒绝。”其中ai保证在Tt1Ta1|t2Ta2|...|tkTak|t1a1|...|tkak不是歧义CFG。这样，如果AMBIGCFG是可判定的，则有PCP可判定的，而PCP是不可判定的，导出矛盾。所以可以得到AMBIGCFG是不可判定的。5.x证明：举反例：令A={M|M是图灵机}。则A满足问题xxx中的条件a,不满足条件b。但是A是可判定的，只要证明M是否符合图灵机的形式定义即可。因此，只满足条件a,不满足条件b不能导出不可判定。令B={M1},其中M1是一台图灵机。则B满足问题xxx中的条件b,不满足条件a。但是B是可判定的。因此，只满足条件b,不满足条件a不能导出不可判定。5.24证明：对任意字符串x，令f1(x)=0x。则有xATMf1(x)=0x∈J。即有ATM≤mJ。进一步有TMAmJ。由TMA图灵不可识别知J图灵不可识别。对任意字符串x，令f2(x)=1x。则有xATMf2(x)=1x∈J。即有TMAmJ。由TMA图灵不可识别知J图灵不可识别。5.25给出一个不可判定语言B的例子，使得B≤mB。解：可利用第10题的结果。令B为5.24中的J，则J≤mJ。构造归约函数如下F=“输入w，1）对w的第一位取反，即0变1，1变0。2）输出w。”则F把J映射归约到J。而J又是不可判定的。5.26证明：(a)判定A2DFA的算法如下：L=“对于输入M，x，其中M是2DFA，x是串，1)计算M的状态个数q，和x的长度n。2)在x上模拟Mqn2步，或直至它停机；3)若M停机，则当M接受时接受，拒绝时拒绝。若未停机，则拒绝。”因为M有q个状态，所以对长度为n的输入，M至多有qn2个不同格局(注意：带上的内容不会改变)。若模拟qn2步还未停机，则必定是进入了循环，该情况下应拒绝。(b)构造从ATM到E2DFA的补的映射归约函数。对于任意给定的M,ω，f(M,ω)=B是如下的2DFA的描述：B=“输入x,若x=#C1#C2#…#Cm#是M在ω上的接受计算历史，即检查x满足：a)C1是M在ω上的起始格局。b)每个Ci+1都是Ci的合法结果。c)Cm是M的一个接受格局。则接受。”条件a,c较容易验证。验证b时，B的两个读头分别在Ci和Ci+1的相应位置上移动，验证结果是否适当。由B的构造可以看到M,ωATMf(M,ω)=BE2DFA此即ATM映射可归约到E2DFA的补。由ATM不可判定，知E2DFA不可判定。5.27证明EQ2DIM-DFA不可判定。证明：下面证明ATM映射可归约到EQ2DIM-DFA的补：对于任意M,w，f(M,w)=G,H是如下的两个2DIM-DFA的描述，其中H满足L(H)=。为构造G，记格局序列C1,C2,…,Cm的编码为C1,C2,…,Cm，它是由格局序列C1,C2,…,Cm组成的矩形串。其由下至上分别是C1,C2,…,Cm，一个格局一行，较短的在右边补上适当数量的空格，四周是由#围成的方框。G=“输入串x，若x=C1,C2,…,Cm是M在w上的接受计算历史，即x满足：a)C1是M在w上的起始格局。b)每个Ci+1都是Ci的合法结果。c)Cm是M的一个接受格局。则接受。”由G,H的构造可以看到M,wATMf(M,w)=G,HEQ2DIM-DFA此即ATM映射可归约到EQ2DIM-DFA的补。由ATM不可判定，知EQ2DIM-DFA不可判定。