计算理论习题答案CHAP5new

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.5 证明ATM不可映射规约到ETM。

证明：反证法

假设ATM?mETM， 则有ATM?mETM。而ATM的补不是图灵可识别的，从而可知ETM的补也不是图灵可识别的。 下面构造一个识别ETM的补的图灵机S： S=“输入，M是TM,

1) 对i=1,2,?重复下一步。

2) 对S1,S2,?,Si模拟M运行i步，若有接受，则接受。” S可识别ETM的补，所以ETM的补是图灵可识别的，与上面由假设得到的ETM

的补不是图灵可识别的矛盾。所以ATM不可映射规约到ETM。 5.7证明：如果A是图灵可识别的，且A≤mA，则A是可判定的。 证：∵A≤mA?A≤mA

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

∴由A和A都是图灵可识别的可知A是可判定的. 5.8 解：在由构造相应骨牌簇时，添加如下一类骨牌：

若M中有一个左移?(q,a)=(r,b,L)，则添加一张骨牌：

?#qa?。 ??#rb??

?#?并且第一张骨牌改为?。 ??##q0w?问题

5.x 证明所有的图灵可识别问题都映射可规约到ATM。

证明：设问题A是图灵可识别的，且M是识别A的TM。构造一个可计算函数f

使得f(w)=， 则有

w?A?f(w)? ATM。

这说明A≤m ATM。

5.9 证明S={|M是TM且满足：只要它接受w，就接受wR}不可判定。 证明：对任意，其中M是TM，w是串，令f()是如下TM： F=“输入x，

1) 若x?01或10，则拒绝。 2) 若x=01，则接受。

3) 若x=10，则在w上运行M。若M接受，则接受。”

可以看到?ATM? f()?S。ATM≤mS，所有S不可判定。

5.10 证明S={|双带TM M在输入w上运行时会在第二条带上写下一个非空白符}是不可判定的。

证明：对任意，其中M是单带确定TM，w是字符串。令f()=，其中D是如下的双带TM： D=“输入x，

1) 初始化，x放在第一带上，第二带为空。 2) 在第一带上模拟M运行。

3) 若M接受，则在第二带上写下一个非空白符，并接受；若M拒绝，则

拒绝。”

从D的构造可以看出?ATM??S，即ATM≤mS，所以S不可判定。 5.13 USELESSTM ={| N是TM,并且N有无用状态}。

求证USELESSTM不可判定。

证明：构造ETM到USELESSTM的规约函数:

F=“对于输入,M=(Q,?,?,?,q0,qaccept,qreject)是TM, 1) 构造TM N

N=(Q,?1,?1,?1,q0,qaccept,qreject)，其中，

?1=??{$},?1=?1?{$}。设Q={q0,q1,q2,?,qn,qreject ,qaccept }。

对任意q?Q，a??1：

??(q,a),a?$,??1(q,a)??(qi?1,$,L),a?$,q?qi,0?i?n,

?(q,$,L),a?$,q?qn.?reject2) 输出。”

对于任意TM M，如上构造的TM N，除接受状态外，每个状态均非无用状态(若在输入$上运行N，则N遍历q0,q1,q2,?,qn，最后进入qreject并停机)。构造N的目的就是消除M中任何非接受状态为无用状态的可能。因此有：

?ETM? ?USELESSTM ?ETM? ?USELESSTM

所以ETM≤mUSELESSTM而ETM不可判定，因此USELESSTM不可判定。

5.14 考虑这样的问题：检查图灵机在输入w上，当其读写头处于带最左方格时，是否曾经试图将读写头向左移。将这个问题形式化为一个语言，并证明它是不可判定的。

解：此问题可以形式化为一个语言S：

S={ | TM M在输入w上，当其读写头处于带最左方格时，曾经

试图将读写头向左移}

为证明S是不可判定的，可以证明ATM≤mS。构造一个可计算函数f:∑*?∑

*

,使得对每个，其中M是TM，w是串，f()=，其中 M’=“输入x,

1) 将工作带上内容改为$x。

2) 读写头置于x的第一个字符，模拟M运行。 3) 每当读写头移到$，保持状态，右移一格。

4) 若M进入接受状态，读写头左移到$,再左移一次，停机，接受；

若M进入拒绝状态，则拒绝。”

于是?ATM??S。

5.15 证明S={|图灵机M在输入w上运行时有左移}可判定。 证明：构造如下TM F：

F=“输入，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=“对输入的骨牌序列

,

扫描骨牌序列。若所有的骨牌的上面的1的个数都大于下面的1的个数，或都小于下面的1的个数，则拒绝。否则，接受。”

S判定这样的PCP。

5.18证明PCP在二元字母表上，即在字母表Σ={0，1}上，是不可判定的。 证明：要想证明该PCP(记为PCP2)是不可判定的，只须证明ATM≤mPCP2。为此需要利用定理5.11的证明过程和规约的传递性：

首先，把书中的PCP任一实例P映射到PCP2的实例P2 设计从P到P2的规约函数如下： F=“对输入

，其中P是PCP：

1) 造 PCP P2，对P中所有骨牌中包含的字符串进行Huffman编码，形成一一对应的只含0和1的字符串(也可进行定长编码)。