计算理论习题解答

计算理论习题解答

练习

1.1 图给出两台DFA M1和M2的状态图. 回答下述有关问题.

a. M1的起始状态是q1 b. M1的接受状态集是{q2} c. M2的起始状态是q1

d. M2的接受状态集是｛q1，q4｝

e. 对输入aabb,M1经过的状态序列是q1，q2，q3，q1，q1 f. M1接受字符串aabb吗？否 g. M2接受字符串ε吗？是

1.2 给出练习2.1中画出的机器M1和M2的形式描述.

M1=(Q1,Σ,δ1,q1,F1) 其中 1） Q1={q1,q2,q3,}; 2） Σ={a,b}; 3） δ1为： q1 q2 q3 a b q2 q1 q3 q3 q2 q1 4） q1是起始状态 5） F1={q2}

M2=(Q2,Σ,δ2,q2,F2) 其中 1） Q2={q1,q2,q3,q4}; 2） Σ={a,b}; 3）δ2为： q1 q2 q3 q4 4） F2={q1,q4}

1.3 DFA M的形式描述为 ( {q1，q2，q3，q4，q5}，{u,d},δ,q3，{q3}),其中δ在表2-3中给出。试画出此机器的状态图。

d d d d u q1 q2 q3 d q4 q5 u u u u

- 1 -

a b q1 q2 q3 q4 q2 q1 q3 q4 3） q2是起始状态

1.6 画出识别下述语言的DFA的状态图。

a){w | w从1开始以0结束}

1 1 1 0

0 0 0,1

b){w | w至少有3个1}

0 0 0 0,1

1 1 1

c) {w | w含有子串0101} 1 0 0,1 0 0 1 0 1

1

d) {w | w的长度不小于3，且第三个符号为0}

1 0 0,1

0,1 0,1 0

1 0,1

e) {w | w从0开始且为奇长度，或从1

0,1 开始且为偶长度}

0 0,1 或 0 0,1 0,1

1 0,1 1

0,1 f) {w | w不含子串110} 0 1 0,1 1 1 0 0 - 2 -

g) {w | w的长度不超过5} 0,1

0,1 0,1 0,1 0,1 0,1 0,1

h){w | w是除11和111以外的任何字符}

1 1 1

0 0 0 0,1

i){w | w的奇位置均为1}

1

0 0,1

0,1 j) {w | w至少含有2个0，且至多含有1个1}

1

0 0 1 1 1 0,1

0 0 1 1

0 0 k) {ε,0} 0

0,1 0,1

1 l) {w | w含有偶数个0，或恰好两个1}

1 1 1

1 0 0 0 0 0 0 0 0 1 1 1

1 m) 空集 n) 除空串外的所有字符串

0,1 0,1 0,1 给出识别下述语言的NFA，且要求符合规定的状态数。

- 3 -

1.7

a. {w | w以00结束}，三个状态 0,1

0 0

b. 语言｛w | w含有子串0101，即对某个x和y，w=x0101y｝，5个状态.

g. 语言0*，1个状态。

0

2.11证明每一台NFA都能够转换成等价的只有一个接受状态的NFA。

证明:设NFA M={Q，Σ,δ,q0,F}，F={ri1，??，rik}.添加一个状态p后，ri1，??，rik分别向p引ε箭头，将ri1，??，rik变为非接受状态，p变为接受状态。又因为添加ε箭头不影响NFA识别语言，所以命题成立。

2.14 a 证明：设M是一台语言B的DFA，交换M的接状态与非接受状态得到一台新的DFA，则这台新的DFA是识别B 的补集，因此，正则语言类受在补运算下封闭。

b 举例说明：设M是一台识别语言B的NFA，交换M的接受状态与非接受状态得到一台新的NFA，

这台新的NFA不一定识别B的补集。NFA识别的语言类在补集下封闭吗？解释你的回答。 解：

a. M是DFA, M是{Q,∑,δ,q0,F},令N={Q,∑,δ,q0,Q-F},设ω=ω1ω2…ωn是字母表上任意字符串，

- 4 -

0,1 0 1 0 1 0,1 c. 语言｛w | w含有偶数个0或恰好两个1｝，6个状态。

1 0 ? 0 ? d. 语言｛0｝，2个状态。

1 0 0 1 1 0 0 e. 语言0*1*0*0，3个状态。

0 ? f. 语言{ε}，1个状态。

1 0 0

因为M与N均为DFA,所以必然存在Q中状态序列r0,r1,…,rn,使得：r0=q0, δ(ri, ωi+1)=ri+1, i=0,…,n-1

1)若rn?F 则ω?B;

2)若rn?F,则rn?Q-F,即N接受ω，若ω?B, 所以N接受B的补集，即B的补集正则。 所以，正则语言类在补运算下封闭。

0 b. 设B为{0}。NFA M：

可识别它。

0 依题对它作变换，得到N：

则N识别的语言{ε}不是B的子集。所以交换M的接受状态与非接受状态得到的新的NFA不一定识别B的补集。

但是由于NFA识别的语言类与DFA识别的语言类相同，即正则语言类。由a的证明，正则语言类在补运算封闭，可知，NFA识别的语言类---正则语言类在补运算下封闭。

若NFA识别语言A，必有 等价的DFA识别A,从而由a知，可交换DFA的接受与非接受状态构造识别A的补集的DFA,则必有等价的NFA识别A的补集。只是，该NFA未必有原NFA交换接受与非接受状态构造而成。

1.15 给出一个反例，说明下述构造不能证明定理2.24，即正则语言类在星号运算下封闭。设N=（Q1,Σ,δ

。N应该识别A1*。 1,q1,F1）识别A1。如下构造N=（Q1,Σ,δ1,q1,F1）

a. N的状态集是N1的状态集。

b. N的起始状态是N1的起始状态相同。

c. F=｛q1｝∪F1。F的接受状态是原来的接受状态加上它的起始状态。

d. 定义δ如下：对每一个q属于Q和每一个a属于Σ。

??1(q,a), 若q?F1 或 a???(q,a)????1(q,a)?{q1}, 若q?F1 且 a??

解：设N1识别语言A={至少含有一个1}，其中输入字母表为{0，1}，可知A*={空串或至少含有一个1}。 a 0,1 0,1 N1: N:

a,b 1 1 2 b ?

按上述规定构造N的状态图如上。可以看出L(N)={0,1}*不等于A*. 所以如此构造的N不一定识别A*.

1.16 使用定理2.19中给出的构造，把下图中的两台非确定型有穷自动机转换成等价的确定型有穷自动机。

0,1 0,1 ? 1 1 2 a)， b)， a a a,b 3 b - 5 -

a. {0n1n0n1n | n?0}

pppp

假设语言上下文无关，设p为泵长度，取S=0101.由泵引理知，S可以划分为uvxyz且满足泵引理条件。

22

考察子串vxy,首先，它一定横跨S的中点，否则，若vxy位于S的前半段，由于|vxy|?p, 则uvxyz中1

nnnn

将是后半段字符串的第一个字符，即不可能是0101的形式。同理，vxy也不可能位于S后半段的位置上。

pijpnnnn

但是,若vxy跨越S的中点时，将S抽取成uxz，它形如0101,i，j不可能都为p，即uxz不可能是0101的形式。

综上，可知S不能被抽取，因此，该语言不是上下文无关的。

b. {0n#02n#03n | n?0}

p2p3p

假设语言上下文无关，设p为泵长度，取S=0#0#0, 由泵引理知，S可以划分为uvxyz且满足泵引理条件。考察子串vxy。首先，v,y中不能有#，否则S抽取成uxz后，其中#个数?1。由条件3，vxy或者位于第2个#之前，或者位于第1个#之后。下面讨论这两种情况：

22

①． 此时，uvxyz中第3部分0的个数保持不变，而前面部分的0的个数至少有一个增加，因此，

22

uvxyz不在该语言中。

22

②． 此时，uvxyz中第1部分0的个数保持不变，而第2，3部分0的个数至少有一个增加，也有

22

uvxyz不在该语言中。

因此，该语言不是上下文无关的。 c. {w#x | w,x?{a,b}*, w是x的子串}

pppp

假设该语言上下文无关，设p为泵长度，取S=01#01, 由泵引理知，S可以划分为uvxyz且满足泵引理条件。显然，v,y中不包含#，不然抽取后的S=uxz中将不含#从而不在该语言中。

22

子串vxy不能落在#的左侧，否则uvxyz中#左侧的字符串长度将大于右边。 子串vxy不能落在#的右侧，否则uxz中#左侧的字符串长度也会大于右边。 现在假设#?x，则必存在不全为0的i,j，使得vy=1i0j，下面分两种情况考虑：

①． j?0, 则uxz=0p1p-i#0p-j1p不在该语言中 ②． j=0, 则uv2xy2z中#左侧的字符串长度大于右边，不在该语言中。

因此，该语言不是上下文无关的。

d. {x1#x2#?#xk | k?2, 每一个xi?{a,b}*, 且存在xi＝xj}

pppp

假设该语言上下文无关，设p为泵长度，取S=ab#ab, 由泵引理知，S可以划分为uvxyz且满足泵引理条件。显然，v,y中不包含#，不然抽取后的S=uxz中将不含#从而不在该语言中。

22

子串vxy不能落在#的左侧，否则uvxyz中#左侧的字符串长度将大于右边。 子串vxy不能落在#的右侧，否则uxz中#左侧的字符串长度也会大于右边。

pijp

于是vxy跨越#两侧.此时，S经抽取成uxz后，具有ab#ab的形式，其中，i,j不全为p。因此，uxz不在该语言中。

综上该语言不是上下文无关的。

2.34 考虑语言B=L(G), 其中G是练习3.13中给出的文法。定理3.19关于上下文无关语的泵引理称存在关于B的泵长度p。p的最小值等于多少？要求给出证明。

证明：p的最小值为4。令D={0i#0j#0k | i, j, k?0}, E={0i#02i | i?0}, 则L(G)=D?E。

L(G)中长度为1的字符串仅有#,不能被抽取。 L(G)中长度为2的字符串仅有#,也不能被抽取。

D中长度?3的字符串必含有0，所以一定可以被抽取。

E中长度?3的字符串也可以被抽取(E中没有长度等于3的字符串)。只需令uvxyz分别为v=0,x=#,y=00, u,z为两边其余的字符串即可。注意到此时|vxy|＝4。

但是泵长度不能等于3。因为若p=3，则要求|vxy|?3，但是对于E中的字符串来说，每在#左边抽取1个0，则同时必须在#右边抽取2个0，即|vy|?3，又x必须包含#, 所以任何有效的抽取必有|vxy|?4。

- 21 -

综上所述，p的最小值为4。

2.35 设G是一个含有b个变元的乔姆斯基范式CFG。证明：如果G产生某个字符串使用了至少2b步的派生，则L(G)是无穷的。

T

R 证明：设G产生字符串S需要至少2b步。

由于一个分支点(变元)对应一次派生，所以S的语法树τ至少有2b个分支点。又由于在乔姆斯基范式下，一个分支点至多有两个子分支点(这意味着层数?n

R b

的结点个数?2－1)，从而τ的由分支点组成的子树的高度大于等于b+1。τ有一条路径上分支点(变元)个数?b+1。由鸽巢原理：必有某个变元R在该路

u v x y z

径上出现至少两次。不妨假设R出现在路径上最下面的b+1个变元中。

按上图所示，将S划分为uvxyz，在每一个R的下面有一棵子树，它产生S的一部分。上面的R有一棵较大的子树，产生vxy，下面的R有一棵较大的子树，产生x，由于这两棵子树由同一个变元产生，因而可以相互替换。这里采用如下操作：反复用较大子树去替换较小子树，则我们得到对于任意n>1, uv nxy n

z?L(G)。

所以若我们能证明v,y不全为ε，则L(G)是无穷的。

?事实上，由乔姆斯基范式的特点，上面一个R的派生选择的必为R?AB形式的规则，而且不可能有A??

?和B??，所以v,y不全为?。从而命题得证。

2.26 给出一个语言，它不是上下文无关的、但满足泵引理的三个条件。要求给出证明。 解：令A＝{aibjckdl | i,j,k,l?0, 且当i=1时，j=k=l}，则：

(1) A满足泵引理的三个条件。取泵长度p＝1。对A中任意长度大于1的字符串s= aibjckdl ，分情况可以如下抽取：

若i=1,则j=k=l, 取v=a,uxy=?，z= bjcjdj, 则对?n?0，uvnxynz= aibjcjdj ?A；

若i?2，且j,k,l不同时为0，不妨设j?0，取u=ai,v=b,xy=?，z= bj-1ckdl, 则对?n?0，uvnxynz= aibj-1+nckdl ?A；

若i?2，且j=k=l=0, 取u=ai-1,v=a,xyz=?, 则对?n?0，uvnxynz= ai-1+n?A； 若i=0，则j,k,l不同时为0，不妨设j?0，取v=b,uxy=?，z= bj-1ckdl, 则对?n?0，uvnxynz=bj-1+nckdl ?A。

(2) A不是上下文无关语言。事实上，若A为上下文无关语言，另取正则语言R=ab*c*d*，由问题3.17可知，L?R是上下文无关的。但这与L?R={abncndn | n?0}不是一个上下文无关语言矛盾。因此，A不是上下文无关的。

3.3 修改定理3.10以得到推论3.12的证明，即证明一个语言是可判定的当且仅当有非确定的TM判定它。 证明：若M是一个确定型判定器则，则M也是一个非确定型判定器。 现在设N是一个非确定的判定器，将构造一个与之等价的确定型判定器M。模拟过程使用深度搜索。 设N的不确定性分支的最大个数为b。

M有三个带：一个输入带，一个工作带，一个地址带。M按深度优先方式搜索N的不确定计算分支树。 M= “输入w，

1) 初始化，第一带上为w, 第二带为空，第三带为1;

- 22 -

2) 将第一带的内容复制到第二带上，

3) 按当前地址位数字选择N的一个不确定性分支，在第二带上模拟N运行一步； 4) 若当前地址位为i

转第2步；

5) 若当前地址位为i＝b，且当前选择无效或按当前选择进入拒绝状态，则将当前地址位改为空

格, 左移并将当前地址位改为空格直到找到一个地址位其值

6) 若N进入接受状态，则接受；否则，右移一格，将空格上写入1，转第三步。”

由于N是非确定型判定器，所以对任意输入，由本题的提示M一定会停机。

3.4 给出枚举器的形式定义。

解：枚举器E=(Q,?,?,?,q0,qaccept,qreject), 其中转移函数?为： ?：Q×??Q×?×{L,R}×?* ? (q,a)=(r,b,s1,c) 表示若E处于状态q,且在工作带上读到a，则状态转移为r，当前格改写为b并按s1作相应左或右移，打印带上写下字符串c，其中若c等于?，则不打印。 另外E的起始格局只能是q0v，这里v表示一个空格。

3.x 检查图灵机的形式定义，回答下列问题并解释你的推测： a． 图灵机能在它的带子上写下空白符吗 b．带字母表?和输入字母表?能相同吗？

c．图灵机的读写头能在连续的两步中处于同一个位置吗？ d．图灵机能只包含一个状态吗？ 解：

a．能。因为空白符属于带字母表?；

b．不能。因为空白符不属于输入字母表?；

c．能。当读写头处于左端点时，如果转移是向左转移，因为不准机器从带的左端点移出，所以下一个格

局读写头仍在左端点。

d．不能。因为qaccept?qreject，至少应有两个状态。

3.6 解：因为M不一定是判定器，可能会在运行某个si时不停机，则L(M)中按字典序大于si的字符串不可能被枚举出来。

3.7 解：因为图灵机的一个本质要求是一步之内，只能做有限的工作，而第1)步中取所有可能的值，这有无限多种情况。 3.8

构造具有3条带的图灵机。 对于问题a.

1) w 先读入第一条带，然后读到0就把0写入第2条带，读到1就把1写入第3条带，直到读到空

格为止。

2) 然后把3个读写头都返回到最左边。

3) 开始读第2条带和第3条带，每次都是读一个字符，如果同时遇上空格符，则接收，否则拒绝。 对于问题b:

1) 和a的第1步相同。

- 23 -

2) 和a的第2步相同。

3) 每次读带3的一个字符就读带2的两个字符，如果同时遇上空格符，就接收，否则拒绝。 对于问题c:

1) 和a的第1步相同。 2) 和a的第2步相同。

3) 每次读带3的一个字符就读带2的两个字符，如果同时遇上空格符，就拒绝，否则接受。

3.x由题知,1-pda代表一个栈的下推自动机,2-pda代表两个栈的下推自动机。如果能用2-pda模拟一个图灵机,而我们已经知道图灵机比下推自动机强大，那么就有2-pda比1-pda更强大。设有TM S。下面构造2-pda P，且记其两个栈分别为A，B：

P＝“对于输入w,

1) 将w读入栈A，再全部从栈A中依次弹出并读入栈B。

2) 模拟S在w上运行。记录S的当前状态，并且栈B的栈顶字符为S的读写头所指方格的字符：

a) 若S执行一个右移?(q,a)=(r,b,R)，则将栈B的栈顶字符a替换为b，弹出b，推入栈A，记录

S的当前状态r。

b) 若S执行一个左移?(q,a)=(r,b,L)，首先将栈B的栈顶字符a替换为b；若栈A不空，则将栈A

弹出一个字符推入栈B；若栈A为空(对应于S处于工作带最左端)，则不作栈操作。记录S的当前状态r。

3) 若S进入接受状态，则进入接受状态。”

由上知.我们用2-pda模拟了图灵机,所以2-pda比1-pda强大.

下面用一个四带TM S来模拟一个3-pda P，要求P进入接受状态之前排空栈，并且或者推入或者弹出：

记P的三个栈为A,B,C。S的四个带，第一带用来模拟P的输入带，第二,三,四带分别模拟栈A,B,C： S＝“对于输入字符串w，

1) 初始化，第一带放入w，第二，三，四带为空。 2) 模拟P分别在四个带上按如下方式动作：

a． 若P在输入带上读一个非空字符，则读第一带字符并右移一格；

若P在输入带上读一个?，则在第一带上不读字符，且读写头保持不动。

b． 栈A,B,C中若有弹出，则在相应带上当前格改写为空格，并左移一格；若有推入a，则

在相应带上右移一格，并写入a。

3) 若P进入接受状态，则接受。”

3.10证明双无限带图灵机识别图灵可识别语言。

证明思路：利用双无限单带图灵机模拟普通单带图灵机时，只需要设计一个左端点。我们的证明是让它在第一格左边标记“$”作为左端点。 证明：

首先用单带双无限带图灵机模拟普通单带图灵机：

设有普通图灵机M1＝( Q1, ?, ?1, ?1, q0, qaccept, qreject )。 下面构造与之等价的单带双无限带图灵机M2＝( Q2, ?, ?2, ?2, qs, qaccept, qreject )，其中

Q2=Q1?{qs,qt}, qs为新的起始状态；?2＝?1?{$}. 对任意q?Q2, a??2,

- 24 -

若 q?qs,?(qt,a,L),?若 q?qt,?(q0,$,R), ?2(q,a)????1(q,a),若 q?Q1 , a??1,??(q, $, R)，若 q?Q1 , a?$.再用普通单带图灵机模拟单带双无限带图灵机：

设有单带双无限图灵机M1＝(Q,?,?,?,q0,qaccept,qreject)，下面构造普通单带图灵机M2： M2=“输入串w，

1) 将带上字符串改写为$w, 将读写头放在w的第一个字符上， 2) 按照M1的转移函数运行，

3) 每当读写头移到了$上，就将$右边的所有字符右移一格，并在$右边的方格里写上空格符，再

将读写头放在这个方格上，转第二步，

4) 若进入接受状态，则接受；若进入拒绝状态则拒绝。”

也可以用普通双带图灵机模拟单带双无限带图灵机：

设有单带双无限图灵机M1＝(Q,?,?,?,q0,qaccept,qreject)，下面构造普通双带图灵机M2： M2=“输入串w，

1) 在第一个带上放上$, 读写头放在$上；

第二个带子上放入#w, 读写头放在第二个方格上。 2) 当第一带读写头位于$上，而第二带读写头不在＃上时，在第二带上按照M1的转移规则运行，

直到停机或读写头移到#上。若进入接受状态则接受，若进入拒绝状态则拒绝。若读写头移到#上，则将第一带上读写头右移一格。

3) 当第二带读写头位于#上，而第一带读写头不在$上时，在第一带上按照M1的转移规则运行，

但是每一步要将读写头移动方向反向，直到停机或读写头移到$上。若进入接受状态则接受，若进入拒绝状态则拒绝。若读写头移到$上，则将第二带上读写头右移一格，转第二步。”

3.11只写一次图灵机是一个单带图灵机，它在每个带方格上最多只能改变其内容一次(包括带上得输入区域)。证明图灵机模型的这个变形等价于普通的图灵机模型。

证明：普通单带图灵机总是可以模拟只写一次图灵机。下面说明怎样用一个只写一次TM T 模拟一个普通单带TM S。

T=“对于输入w=w1w2?wn,

1) 在w1w2?wn上并模拟S运行。

2) 每当S要改写工作带时(例如设S要将当前方格内容改写为b，并且左移或右移一格)，T按如下方

式动作：

a. 将当前方格改写为“b*”，在带子右边第一个空格写下“#”。

b. 将“#”左边的字符抄写到“#”右边(注：每抄写一个字符，需要将此格字符改写一次以作上标记，但是“b*”不用再作另外标记，而且将“b*”抄写为“b~”)。

c. 找到带有标记“~”的字符，再模拟S左移或右移一格。 然后继续模拟S。

3) 若S接受则接受；若S拒绝则拒绝。” 3.12

对于普通图灵机N，构造与之等价的带左复位的图灵机E： E＝“对于输入w,

1) 在w上模拟N的一步动作：

- 25 -

若N要将当前格由a改为b且右移，则照此动作；

若N要将当前格由a改为b且左移，则将当前格由a改为b#且复位： a) 以~标记当前位，右移一格；

b) 若当前位没有标记#，则复位，右移直到找到标记有~的字符，去掉此标记，右移一格转步(a); c) 若当前位有标记#，则去掉标记#并复位，右移或直到找到标记有~的字符，去掉此标记； 2) 若N进入接受状态，则接受；若进入拒绝状态，则拒绝；否则转第一步。” L(E)=L(N)。因此左复位的图灵机识别图灵可识别语言类。

3.13 以停留代替左移的图灵机识别什么语言类？

解：正则语言类。首先一个DFA可以被一个以停留代替左移的图灵机模拟。下面证明一个以停留代替左移的图灵机S=(Q,?,?,?,q1,qaccept,qreject)，可以被一个NFA M=(Q1,?,?1,q0,F)模拟。

M的构造如下：

令Q1= Q×???{qend}， F={qend}，q0=(q1,?), 1) 对任意q?Q-{qaccept,qreject}, a??,令

?1( (q,?) , a )={(q,a)};

2) 对任意q?Q-{qaccept,qreject}, a??,

若有转移?(q,a)=(r,b,R)，则令?1( (q,a), ? )={(r, ?)}; 若有转移?(q,a)=(r,b,S)，则令?1( (q,a), ? )={(r,b)}; 3) 对任意a???, b??，

令?1( (qaccept,a) , b )={(qaccept, ?)};

4) 对任意q?Q，令Sq=(Q,?,?,?,q,qaccept,qreject),

若??L(Sq)，则令?1( (q,?) , ? )={qend}。 其中第一类转移是用来读字符的。

第二类转移是用来模拟S的读写头的移动的。由于S没有左移，所以右移一格之前改写的内容b可以舍去。

第三类转移用来处理当S已进入接受状态，但是字符串还没有读完的情况的。即先由?1( (qaccept,a) , b )={ (qaccept,?) }读完所有剩余字符，再由第四类转移中的?1((qaccept,?),?)={qend}进入接受状态。

第四类转移用来处理S的读写头移出输入区域的情况的，在这种情况下，S是进入接受状态，还是进入拒绝状态，还是不停机，完全取决于进入空白区域时的状态q：即若??L(Sq)，则S最终会进入接受状态；若??L(Sq)，则S最终会进入拒绝状态或不停机。

3.15 证明可判定语言类在下列运算下封闭。

a. 并。

证明：设M1，M2为识别可判定语言A1,A2的判定器。构造图灵机M： M＝“输入w，

1) 分别在w上运行M1和M2，每运行一步M1就运行一步M2。 2) 若M1和M2中有一个接受，则接受。

若都拒绝，则拒绝。”

M为识别A1?A2的判定器。所以可判定语言类对并运算封闭。 b. 连接。

证明：设M1，M2为识别可判定语言A1,A2的判定器。构造图灵机M： M＝“输入w，

1) 列出所有将w分成两段的方式(|w|+1种).

2) 对于每一种分段方式，在第一段上运行M1，在第二段上运行M2。若都接受，则接受。 3) 若没有一种分段方式被接受则拒绝。”

- 26 -

M为识别A1?A2的判定器。所以可判定语言类对连接运算封闭。 c. 星号。

证明：设M1为识别可判定语言A的判定器。

M＝“输入w，

1) 列出w的所有分段的方式(2|w|-1种)。 2) 对于每一种分段方式，重复下列步骤：

3) 分别在每一段上运行M1，若每一段都能被M1接受，则接受。 4) 若没有一种分段方式被接受则拒绝。”

M为识别A*的判定器。所以可判定语言类对星号运算封闭。 d. 补。

证明：设M1=(Q,?,?,?,q0, q1, q2)为识别可判定语言A的判定器，其中q1为接受状态，q2为拒绝状态。令M=(Q,?,?,?,q0, q2, q1)，其中q2为接受状态，q1为拒绝状态。则M为识别A的判定器。所以可判定语言类对补运算是封闭的。 e. 交。

证明：设M1，M2为识别可判定语言A1,A2的判定器。构造图灵机M： M＝“输入w，

1) 分别在w上运行M1和M2，每运行一步M1就运行一步M2。 2) 若M1和M2中都接受，则接受。

若M1和M2中有一个拒绝，则拒绝。”

M为识别A1?A2的判定器。所以可判定语言类对交运算是封闭的。

3.16 证明图灵可识别语言类在下列运算下封闭： a．并 b．连接 c．星号 d．交

证明：要证这四种运算下图灵可识别语言类封闭，只需设计出图灵机来识别此种语言。设A和B是图灵可识别语言，A=L(M1)，B=L(M2)，M1和M2是两个图灵机。 a．M=“对于输入w：

1) 在输入w上并行运行M1和M2；

2) M1和M2中有一个停机且接受，则接受；若都停机且拒绝，则拒绝。” M识别A1?A2。所以图灵可识别语言类对并运算是封闭的。 b. M＝“输入w，

1) 出所有将w分成两段的方式(|w|+1种). 2) 对于i=1,2,?重复以下步骤：

3) 对于每一种分段方式，在第一段上运行M1i步，在第二段上运行M2 i步，或者直到停机。若

都接受，则接受。”

M识别A1?A2。所以图灵可识别语言类对连接运算是封闭的。 c．M＝“输入w，

1) 列出w的所有分段的方式(2|w|-1种). 2) 对于i=1,2,?重复以下步骤：

3) 对于每一种分段方式，分别在每一段上运行M1 i步，或者直到停机。

若M1接受所有段，则接受。”

M识别A*。所以图灵可识别语言类对星号运算是封闭的。 d．M= “对于输入w：

4.2 考虑DFA和正则表达式是否等价的问题。将这个问题表示为一个语言并证明它可判定。 解：设EQD-R={|A是DFA,B是正则表达式，L(A)=L(B)}。构造如下TM，

- 27 -

F=“对于输入 , A是DFA，B是正则表达式，

1) 将正则表达式B转化为等价的DFA C。 2) 检测A与C是否等价(EQDFA可判定)。 3) 若等价，则接受；否则拒绝。” F判定EQD-R。

4.3 设ALLDFA={ | A是一个识别?*的DFA}。证明ALLDFA可判定。 证明：

方法一：设计一个使用标记算法的TM M,

M=“对于输入,其中A是一个DFA:

1) 去掉除起始状态以外的所有无用状态。标记起始状态。 2) 重复下列步骤，直到没有新的状态可被标记。 3) 对于每一个未标记状态，如果有一个到达它的转移是从某个已被标记过的状态出发的，

则将其标记。

4) 如果所有的标记状态都是接受状态，则接受；否则拒绝”

方法二：构造DFA B，使得L(B)= ?*。

M＝“对于输入,其中A是一个DFA:

1) 检测是否等价(EQDFA可判定)。 2) 若等价，则接受；若不等价，则拒绝。”

4.4 A?CFG={ | G是一个派生?的CFG}。证明A?CFG可判定。 证明：M=“输入，G是一个CFG，

1) 构造与G等价的Chomsky文法P。

2) 若P的规则集中有S0??(其中S0为起始变元)，则接受；否则拒绝。”

M判定A?CFG。

4.9 设INFTYDFA={|A是一个DFA，且L(A)是一个无限语言}。证明INFTYDFA是可判定的。 证明：要证一个DFA识别一个无限语言，只需证此DFA的状态图中有回路。 M=“对于输入，其中A是一个DFA：

1) 若无接受状态则拒绝。

2) 去掉A中所有无用状态(没有从它出发到达任何接受状态的路径)。

若起始状态被去掉，则拒绝。

3) 重复下一步，直到没有新的状态被标记。 4) 考察每一个未标记的状态，如果没有到它的转移(射入的箭头)，则将其标记并去掉所有从

它出发的转移(射出的箭头)。

5) 若所有状态都被标记，则拒绝；否则接受。”

4.11 设A={|M是DFA，它不接受任何包含奇数个1的字符串}。证明A是可判定的。 证明：构造DFA N，使L(N)={含奇数个1的字符串}。构造图灵机

F=“对于输入，其中M是DFA，

1) 构造DFA D，使L(D)=L(M)∩L(N)。 2) 检测L(D)是否为空。(EDFA可判定检测)。 3) 若L(D)＝?，则接受；否则拒绝。”

4.12设A ={｜R和S是正则表达式，且L(R)?L(S) }，证明A是可判定的。

- 28 -

解：T=“输入，R和S是正则表达式,

1) 构造DFA C，使L(C)＝L(R)?L(S)。

2) 用定理5.4检查L(C)是否为空。 3) 若L(C)为空，则接受；否则拒绝。”

T判定A。

4.13 “检查一个CFG是否派生1*中某个串问题”

解： LX={|G是{0，1}*上的CFG，且1*∩L(G)≠?} 证明：构造TM T

T＝“对于输入，A为CFG

1) 将终结符“1”和“?”做标记。

2) 重复下列步骤，直至无可做标记的变元。 3) 如G有规则A?U1U2…Un，且U1U2…Un中每个符号都已做过标记，则将A做标记，其中

Ui为终结符或非终结符。

4) 如果起始变元没有被标记则拒绝，否则接受。” T判定LX。

4.15 设A ={｜R是正则表达式，其所描述的串中至少有一个串以111为子串}。证明A是可判定的。 证明：构造自动机B，使得L(B)={所有以“111”为子串的字符串}。 S=“在输入上，其中G是一个正则表达式,

1) 将G转化为与之等价的自动机A。 2) 构造C，使得L(C)= L(A)? L(B)。 3) 检测C是否为空(EDFA可判定)。

4) 若C为空，则拒绝；若C不为空，则接受。”

4.16 检查两个DFA在长度小于或对于某个数的所有串上运行，并以此方法证明EQDFA是可判定的。计算一个这样的数。

证明：对于长度k，构造TM

Mk=“输入，A，B是DFA

1) 列出所有长度小于或等于k的串；

2) 在这些串上分别运行A，B；

3) 若A，B同时接受或拒绝，则M接受；若A，B不同时接受或拒绝，则M拒绝。”

因为所有长度?k的串是有限的，Mk一定是可以进入停机状态，所以Mk是一个判定器。而且Mk判定

{ | A,B是DFA,Ck={x??*| |x|?k},且L(A)?C=L(B) ?C}。

构造TM M：

M=“输入，A，B是DFA

1) 计算A和B的状态数p,q。 2) 在上运行Mpq。

3) 若Mpq接受，则接受；否则拒绝。” 下面证明M判定EQDFA。

首先注意到A的任意状态与B的任意状态组成的不同状态对有p×q个。 对于?*上的任意串w=w1w2w3?wL，设在A上运行得到状态序列P1P2P3?PL 和在B上运行得到状态序列Q1Q2Q3?QL。若L>pq, 则在L个状态对(Pi, Qi),i=1,2,?,L, 中必有相同的。不妨设Pi＝Pj, Qi＝Qj, 且i

令u=w1w2?wiwj+1wj+2?wL。则有w?L(A)?u?L(A)，因为这都取决于PL是否属于A的接受状态集。

- 29 -

和w?L(B)?u?L(B)，因为这都取决于QL是否属于B的接受状态集。

若|u|>pq，则按此方法继续减小长度，最后会得到存在v (|v|?pq), w?L(A)?v?L(A)和w?L(B)?v?L(B)。 即L(A)=L(B)?[L(A)?Cpq]=[L(B) ?Cpq]。于是

M接受?[L(A)?Cpq]=[L(B) ?Cpq] ? L(A)=L(B)，

此即M判定EQDFA。

4.17 设C是一个语言。证明C是图灵可识别的，当且仅当存在一个可判定语言D，使得C={ x | ?y (?D)}。

证明：设M是识别语言C的图灵机，N是语言D的判定器，即C=L(M)，D=L(N)；

(1) 首先证明必要性，即“若C是图灵可识别的，则存在一个可判定语言D，使得C={ x | ?y (?D)}”。

N=“对于输入，x是一个串，k是自然数且k≥1， 1) 在x上模拟M运行k步或直到停机。

2) 若M接受，则接受；若M不接受，则拒绝。”

（注：这里实际D={ | x在k步之内被M接受}）

(2) 下面证明充分性，即“若D是可判定语言，则存在图灵可识别语言C，满足C={x | ?y (?D)}”。 M=“输入串x，

1) 取一个y，在上运行D；

2) 若D接受，则接受；若D不接受，则找下一个y(按字典序)，重复第一步。”

综上，命题得证。

4.18 设A和B是两个不交的语言。称语言C分离A和B，如果A?C且B?C。证明任意两个不交的补图灵可识别语言都可以由某个可判定语言分离。

证明：设识别A的补的TM为T，识别B的补的TM为S。注意到L(T)?L(S)= ?*。 D=“输入w，

1) 在w上分别运行T和S，直到有一个首先进入接受状态。 2) 若T进入接受状态，则拒绝；若S进入接受状态，则接受。” D是判定器，而且A?L(D)，B?L(D)。

4.19 设S={ | M是DFA，且只要接受w，就接受wR}。证明S可判定。 证明：构造如下TM： D=“输入,

1) 构造DFA M1使得L(M1)= L(M)R。 2) 检测M1与M是否等价。 3) 若等价，则接受；否则拒绝。”

D判定S。

4.22下推自动机的一个无用的状态是在任何输入上它都不会进入的状态。考虑检查一个下推自动机是否有无用状态问题。将这个问题形式化为一个语言，并证明它是可判定的。 证明：S={

| P是PDA，且没有无用状态}。构造如下判定器D： D=“输入

，P=(Q,?,?,?,F)是PDA，

1) 对于P中的每一个状态q，重复以下步骤。 2) 构造PDA P1=(Q,?,?,?,F1)，其中F1={q}。

- 30 -

3) 检测L(P1)是否为空。若L(P1)=?，则拒绝。 4) 若没有一个为空，则接受。”

4.28设A是由某些图灵机的描述构成的一个图灵可识别语言{,,?}，其中每个Mi都是判定器。求证：存在可判定语言D，它不能由任何一个其描述在A中出现的判定器来判定。 证：设E是A的枚举器。考虑判定器F：

F＝“对输入串x，

1) 初始化，令y＝?。

2) 运行E，每当E输出一个串(判定器)时，计算y按字典序的下一个串，仍将此串记为y。若

y?x,继续运行E。

3) 若y与x相同，则记E此时输出的判定器为。 4) 对串x运行Mi，若Mi接受则拒绝；若Mi拒绝则接受。” L(F)即为所求语言。

1) 在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|. 由(1)和(2)可知结论成立。

3.22 解：A是可判定的。

因为若上帝存在，则s=0，A={0}是可判定的。 若上帝不存在，则s=1，A={1}是可判定的。

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是补图灵可识别的。

- 31 -

证明：注意到ACFG={|G是能派生串w的CFG}是可判定的。构造如下TM： F=“输入，其中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使得：

?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.6 略。

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???- 32 -

并且第一张骨牌改为????。

?##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),??1(q,a)??(qi?1,$,L),?(q?reject,$,L),a?$,a?$,q?qi,0?i?n,

a?$,q?qn.2) 输出。”

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

- 33 -

?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的字

符串(也可进行定长编码)。 2) 输出。”

F将PCP映射规约到PCP2，即PCP≤mPCP2；

- 34 -

其次，有定理5.11有ATM≤mPCP； 根据规约的传递性可知，ATM≤mPCP2

∵ATM是不可判定的， ∴PCP2是不可判定的。

5.21 设AMBIGCFG＝{|G是歧义的CFG}。证明AMBIGCFG是不可判定的。 证明：设AMBIGCFG是可判定的，且R判定AMBIGCFG构造S判定PCP S＝“对于任一PCP输入，如p＝{[t1/b1],[t2/b2],...,[tk/bk]}

1) 利用如下规则构造一个CFG G：

S?T|B

T?t1Ta1|t2Ta2|...|tkTak|t1a1|...|tkak B?b1Ba1|b2Ba2|...|bkBak|t1a1|...|bkak

2) 在上运行R，如果R接受则接受，如果R拒绝则拒绝。” 其中ai保证在T?t1Ta1|t2Ta2|...|tkTak|t1a1|...|tkak不是歧义CFG。

这样，如果AMBIGCFG是可判定的，则有PCP可判定的，而PCP是不可判定的，导出矛盾。所以可以得到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。则有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图灵不可识别。

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是2DFA，x是串，

1) 计算M的状态个数q，和x的长度n。 2) 在x上模拟M qn2步，或直至它停机；

- 35 -

本文来源：https://www.bwwdw.com/article/3wbg.html