计算理论答案汇总

第一章

练习

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为： a b q1 q2 q1 q2 q3 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为： a b q1 q1 q2 q2 q3 q4 q3 q2 q1 q4 q3 q4 3）q2是起始状态 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.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} 0,1 1 0 0 0 1 0 1

1

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

0,1 1 0

0,1 0,1 0

1 0,1

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

0,1

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

0,1

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

1 1 0

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

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,1 0

0,1

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

1

0 0

1 1 0,1

1 0 0

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

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

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

0 0

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

0,1 0,1

0 1 0 1

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

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是字母表上任意字符串，因为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的补集。

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

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

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

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

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

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

*

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

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

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

c. F=｛q1｝∪F1。F的接受状态是原来的接受状态加上它的起始状态。 d. 定义δ如下：对每一个q属于Q和每一个a属于Σ。

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

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

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

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

解：a), b)

a a a,b a 12 121 1 a b b b b

a a,b a,b b 2 23 ? ?

2.13 给出生成练习2.4中语言的正则表达式。(注: 答案不唯一) a. {w | w从1开始以0结束} 1Σ*0. b. {w | w至少有3个1} Σ*1Σ*1Σ*1Σ*. c. {w | w含有子串0101} Σ*0101Σ*. d. {w | w的长度不小于3，且第三个符号为0} ΣΣ0Σ*. e. {w | w从0开始且为奇长度，或从1开始且为偶长度} 0(ΣΣ)*?1Σ(ΣΣ)*.

f. {w | w不含子串110} (0?10) *1*. g. {w | w的长度不超过5} ??Σ?ΣΣ?ΣΣΣ?ΣΣΣΣ?ΣΣΣΣΣ. h. {w | w是除11和111以外的任何字符} 0Σ*?10Σ*?110Σ*?111ΣΣ*. i. {w | w的奇位置均为1} (1Σ)*( ??1). j. {w | w至少含有2个0，且至多含有1个1} 0*(00?010?001?100) 0*. k. {ε,0}. ε?0. l. {w | w含有偶数个0，或恰好两个1} (1*01*0)*1*?0*10*10*. m. 空集. ?. n. 除空串外的所有字符串ΣΣ*.

1.19对下述每一个语言，给出4个字符串，2个是这个语言的成员，2个不是这个语言的成员。这里假设字母表Σ={a,b}.

a. a*b* 成员：ab，aab 非成员：aba，ba b. a(ba)* 成员：ab，abab 非成员：abb，aa c. a*?b* 成员：aaa，bbb 非成员：ab，ba d. (aaa)* 成员：aaa，aaaaaa 非成员：a，aa e.Σ*aΣ*bΣ*aΣ* 成员：aba，aaba 非成员：aa，abb f. aba?bab 成员：aba，bab 非成员：a，b g. (??a)b 成员：b，ab 非成员：a，bb h. (a?ba?bb) Σ* 成员：a，bb 非成员：?，b

1.21 使用引理2.32中叙述的过程，把图2-38中的有穷自动机转换成正则表达式。

a,b 1 2 a a a a), b),

b b a 1 b 2 b 3

解: a) a*b(a?ba*b)*

b) ??(a?b)a*b[(aa?ab?b)a*b]*(a??). (注：答案不唯一)

1.29利用泵引理证明下述语言不是正则的。 a. A1={012| n?0}。

证明：假设A1是正则的。设p是泵引理给出的关于A1的泵长度。

令S=012,

∵S是A1的一个成员且S的长度大于p，所以泵引理保证S可被分成3段S=xyz且满足泵引理的3个条件。根据条件3，y中只含0，xyyz中，0比1、2多，xyyz不是A1的成员。违反泵引理的条件1，矛盾。 ∴A1不是正则的。

b. A2={www | w?{a,b}*}.

证明：假设A2是正则的。设p是泵引理给出的关于A2的泵长度。

令S=ababab,

p

p

p

ppp

nnn

∵S是A2的一个成员且S的长度大于p，所以泵引理保证S可被分成3段S=xyz且满足泵引理的3个条件。根据条件3，y中只含a，所以xyyz中第一个a的个数将比后两个a的个数多，故xyyz不是A2的成员。违反泵引理的条件1，矛盾。 ∴A2不是正则的。

c. A3={a2 | n?0}.(在这里，a2表示一串2个a .)

证明：假设A3是正则的。设p是泵引理给出的关于A3的泵长度。

令S= a2，

∵S是A2的一个成员且S的长度大于p，所以泵引理保证S可被分成3段S=xyz且满足泵引理的3个条件。即对任意的i?0，xyiz都应在A3中，且xyiz与xyi+1z的长度都应是2的幂. 而且xyi+1z的长度应是xyiz的长度的2倍(n?1)。于是可以选择足够大的i，使得|xyiz|=2>p. 但是|xyi+1z|-|xyiz|=|y|?p. 即|xyi+1z|<2∴A3不是正则的。

1.30下面“证明”0*1*不是正则语言，指出这个“证明”中的错误。(因为0*1*是正则的，所以一定错误。) 采用反证法证明。假设0*1*是正则的。令P是泵引定理给出的关于0*1*的泵长度。取S为字符串01。S是0*1*的一个成员，但是例2.38已证明S不能被抽取。于是得到矛盾，所以0*1*不是正则的。

解：在例2.38中的语言是{01 | n?0}，取S为字符串01，S确实不能被抽取；但针对语言0*1*，S是能被抽取的。将S分成三段S=xyz，由泵引理的条件3，y仅包含0，而xyiz属于语言0*1*，即S能被抽取，故题设中的“证明”不正确。

1.24有穷状态转换器(FST)是确定性有穷自动机的一种类型。它的输出是一个字符串，而不仅仅是接受或拒绝。图2—39是两台有穷状态状态转换器T1和T2的状态图。

0/0 1/1 q1

1/0 2/1 a/1 2/1 a/0 q1 b/1 b/0 q2 0/0 q2 b/1 q3 T1 a/1 T2 FST的每一个转移用两个符号标记，一个指明该转移的输入符号，另一个指明输出符号。两个符号之间用斜杠“/”把它们分开。在T1中，从q1到q2的转移有输入符号2和输出符号1。某些转移可能有多对输入-输出，比如T1中从q1到它自身的转移。FST在对输入串w计算时，从起始状态开始，一个接一个地取输入符号w1?wn，并且比照输入标记和符号序列w1?wn=w进行转移。每一次沿一个转移走一步，输出对应的输出符号。例如，对输入2212011，机器T1依次进入状态q1, q2, q2, q2, q2, q1, q1, q1和输出1111000。对输入abbb，T2输出1001。给出在下述每一小题中机器进入的状态序列和产生的输出。

a. T1对输入串011, 输出：000, 状态序列：q1, q1, q1, q1. b. T1对输入串211, 输出：111, 状态序列：q1, q2, q2, q2.

c. T1对输入串0202, 输出：0101, 状态序列：q1, q1, q2, q1, q2。 d. T2对输入串b, 输出：1, 状态序列：q1, q3.

e. T2对输入串bbab, 输出：1111, 状态序列：q1, q3, q2, q3, q2.

f. T2对输入串bbbbbb, 输出：110110, 状态序列：q1, q3, q2, q1, q3, q2, q1。 g. T2对输入串?, 输出：?, 状态序列：q1。

nn

pp

pp

n+1

n

n

p

n

n

n

, 矛盾。

1.25 给出有穷状态转换器的形式定义。

解：有穷状态转换器FST是一个五元组(Q,Σ,Г,δ,q0)

1) Q是一个由穷集合，叫做状态集

2) Σ是一个由穷集合，叫做输入字母表 3) Г是一个由穷集合，叫做输出字母表 4) δ：Q×Σ?Q×Г是转移函数 5) q0是起始状态

FST计算的形式定义：

M=(Q,Σ,Г,δ,q0)是一台由穷状态转换器，w=w1w2?wn是输入字母表上的一个字符串。若存在Q中的状态序列：r0, r1, ?rn和输出字母表上的一个字符串s=s1…sn, 满足下述条件： 1）r0=q0;

2）δ(ri,wi+1)=(ri+1, si+1), i=0,1,?,n-1 则M在W的输入下输出s.

1.26利用你给练习2.20的答案，给出练习2.19中画出的机器T1和T2的形式描述。 解：有穷状态转换器T1的形式描述为：

T1=({q1, q2 }, {0，1，2},δ, q1, {0,1}) 其中转移函数为：

0 1 2 q1 q1/0 q1/0 q2/1 q2 q1/0 q2/1 q2/1 有穷状态转换器T2的形式描述为： T2=({{q1, q2, q3}, {a, b},δ, q1, {0,1}) 其中转移函数为：

a b q1 q2/1 q3/1 q2 q3/1 q1/0

1.27 给出一台具有下述行为的FST的状态图。它的输入、输出字母表都是{0,1}。它输出的字符串与输入的字符串偶数为相同、奇数位相反。例如，对于输入0000111，它应该输出1010010。 解：

1/0

0/1

q1 q2

1/1

0/0 1.46 证明：

a) 假设{010|m,n≥0}是正则的，p是由泵引理给出的泵长度。取s＝010，q>0。由泵引理条件3知，|xy|≤p，故y一定由0组成，从而字符串xyyz中1前后0的数目不同，即xyyz不属于该语

言，这与泵引理矛盾。所以该语言不是正则的。

b) 假设{0n1n|n≥0}的补集是正则的，则根据正则语言在补运算下封闭可得{0n1n|n≥0}是正则的，这

与已知矛盾，故假设不成立。所以该语言不是正则的。

记c={0m1n|m≠n}，┐c为c的补集，┐c∩0*1*={0n1n|n≥0}，已知{0n1n|n≥0}不是正则的。若 ┐c是正则的，由于0*1*是正则的，那么┐c∩0*1*也应为正则的。这与已知矛盾，所以 ┐c不是正则的。由正则语言在补运算下的封闭性可知c也不是正则的。

c) {w | w?{0,1}*不是一个回文}的补集是{w | w?{0,1}*是一个回文}，设其是正则的，令p是由泵引

理给出的泵长度。取字符串s=010，显然s是一个回文且长度大于p。由泵引理条件3知|xy|≤p，

pqp

nmn

pqp

q3 q1/0 q2/1 故y只能由0组成。而xyyz不再是一个回文，这与泵引理矛盾。所以{w | w?{0,1}*是一个回文}不是正则的。由正则语言在补运算下的封闭性可知{w | w?{0,1}*不是一个回文}也不是正则的。

1.31 对于任意的字符串w=w1w2…wn，w的反转是按相反的顺序排列w得到的字符串，记作wR，即wR=wn…w2w1。对于任意的语言A，记 AR={wR | ?A}证明：如果A是正则的，则AR也是正则的。 证明：

因为A是正则语言，所以可以用NFA来表示该语言，现在来构造AR的NFA，将NFA A中的接受态变为中间态，起始态变为接受态，再添加一新的起始态，并用ε箭头连接至原来的接受态，其它所有的箭头反向。 经过变换后得到NFA变成描述AR的NFA.

1.32 令 0 0 0 1 1 ?3= 0 , 0 , 1 , …,

0 1 0 1

?3包括所有高度为3的0和1的列向量。?3上的字符串给出三行0和1的字符串。把每一行看作一个二进制数，令

B={ w??3* | w最下面一行等于上面两行的和}

例如，

0 1 0 1 1

0 0 ?B 0 0 1 ?B ,

1 1 1 0 0

证明B是正则的。 证明：由题设B的定义可知，w上面两行之和减去下面一行结果为零，由此可设计NFA M (Q, Σ, δ, q0, F)，其中?=?3。Q={q0,q1}。q0状态表示上一次运算的进位为0，q1状态表示上一次运算的进位为1。 δ由下表给出： 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 q0 {q0} {q0} {q0} {q1} ? ? ? ? q1 ? {q0} {q1} ? {q1} ? ? {q1} F={q0}

状态图为： 1 1 0 1 1 1 1 0 0 q0 q1 0 , 0 , 0 1 , 0 , 1

1 1 0 1 0 0 0 0

1

所以可知自动机M识别的是语言BR，因此BR是正则的。由题2-24的结论可知B也是正则的。

1.33 令

0 , 0 1 1 , , ?2= 0 1 0 1

?2包含所有高度为2的0和1的列。?2上的字符串给出两行0和1的字符串。把每一行看作一个二进制数，令

C={ w??2* | w下面一行等于上面一行的3倍 }。

证明C是正则的。可以假设已知问题2.24中的结果。

证明：如下的NFA识别CR：其中q0状态表示上一次运算的进位为0，

1 1

1 0 0 1 qqq0 1 2 0 1 0 0

1 0

q1状态表示上一次运算的进位为1, q2状态表示上一次运算的进位为2。

如下的NFA识别C：其中状态q0,q1,q2分别表示目前读到的下面的数减上面 0 0 1 0 0 1 q0 q1 q2 0 1 1 1 1 0 的数的3倍余0,1,2的情况。

1.34令 0 , 0 1 1 , , ?= 2 0 1 0 1 ?2包含所有高度为2的0和1的列。?2上的字符串给出两行0和1的字符串。把每一行看作一个二进制数，令

D={ w??2* | w上一行大于下一行 }。

证明D是正则的。

证明：由题设可设计自动机M=(Q, Σ, δ, q, F)，其中Q={q1,q2}，F={q2}, 转移函数与状态图为： 0 0 1 1 0 1 0 1 q1 q2 {q1} {q2} ? {q2} {q2} {q2} {q1} {q2}

1

0 0 , 1 0 , 0 , 1 , 1 q1 q2 0 1 0 1 0 1

1.35设∑2与问题2.26中的相同。把每一行看作0和1的字符串，令E={w??2* | w的下一行是上一行的反转}，证明E不是正则的。

证明：假设E是正则的，令p是有泵引理给出的泵长度。

p p

选择字符串s= 1 0 。于是s能够被划分为xyz且满足泵引理的条件。

0 1

1 根据条件3，y仅能取包含 的部分，当添加一个y时，xyyz不属于E. 所以E不是正则的.

0 1.36 令Bn={ak | k是n的整数倍}。证明对于每一个n?1, Bn是正则的。

证明：设字母表∑为{a}，则an是一正则表达式。所以，(an)*也是正则表达式。由题意Bn=(an)*,即Bn可以用正则表达式表示。所以，Bn也是正则的。

1.37 令Cn={x | x是一个二进制数，且是n的整数倍}。证明对于每一个n?1, Cn是正则的。 证明：下面的DFA识别Cn：(正向读)

?1(q,a,b),若q?Q1?F1,b?(?1)?,???(q,a,b)?{(q,?)},若q?F1,a?b??,12???(q,a,b)=??1(q,a,b),若q?F1,(a,b)?(?,?),

??2(q,a,b),若q?Q2,b?(?2)?,???,else.?

c. A* 方法一：CFG。设有CFG G1＝(Q1,?,R1,S1)，L(G1)=A。构造CFG G=(Q,?,R,S0)，其中Q= Q1 ?{S0}, S0是起始变元，R= R1?{S0?S0S0|S1|?}. 方法二：PDA。

设P1=(Q1,?,?1,?1,q1,F1)识别A，而且P1满足在接受之前排空栈(即若进入接受状态，则栈中为空)这个要求。

则如下构造的P=(Q,?,?,?,q1,F)识别A*，其中 1) Q=Q1?{q0}是状态集， 2) ?＝?1，是栈字母表， 3) q0是起始状态，

4) F＝F1?{q0}是接受状态集，

5) ?是转移函数，满足对任意q?Q, a???,b???

?1(q,a,b),若q?Q1?F1,???(q,a,b)?{(q,?)},若q?F1,a?b??,11??

?(q,a,b)=??1(q,a,b),若q?F1,(a,b)?(?,?),?(q1,?)若q?q0,a?b??,???,else.?

2.9 证明在3.1节开始部分给出的文法G2中，字符串the girl touches the boy with the flower有两个不同的最左派生，叙述这句话的两个不同意思。 <句子>

?<名词短语><动词短语> ?<复合名词><动词短语> ?<冠词><名词><动词短语> ?a_<名词><动词短语> ?a_girl_<动词短语> ?a_girl_<复合名词>

?a_girl_<动词>< 名词短语> ?a_girl_touches_< 名词短语>

? a_girl_touches_<复合名词><介词短语> ?a_girl_touches_<冠词><名词><介词短语> ?a_girl_touches_the_<介词><复合名词> ?a_girl_touches_the_boy_<介词短语>

?a_girl_touches_the_boy_<介词><复合名词> ?a_girl_touches_the_boy_with_<复合名词> ?a_girl_touches_the_boy_with_<冠词><名词> ?a_girl_touches_the_boy_with_the_<名词> ?a_girl_touches_the_boy_with_the_flower 含义是 ：女孩碰这个带着花的男孩

<句子>

?<名词短语><动词短语> ?<复合名词><动词短语> ?<冠词><名词><动词短语> ?a_<名词><动词短语> ?a_girl_<动词短语>

?a_girl_<复合动词><介词短语>

?a_girl_<动词>< 名词短语><介词短语> ?a_girl_touches_< 名词短语><介词短语> ?a_girl_touches_<冠词><名词><介词短语> ?a_girl_touches_the_< 名词><介词短语> ?a_girl_touches_the_boy_<介词短语>

?a_girl_touches_the_boy_<介词><复合名词> ?a_girl_touches_the_boy_with_<复合名词> ?a_girl_touches_the_boy_with_<冠词><名词> ?a_girl_touches_the_boy_with_the_<名词> ?a_girl_touches_the_boy_with_the_flower 含义是： 女孩用花碰这个男孩

2.10 给出产生语言A={aibjck| i,j,k?0且或者i=j或者j=k}的上下文无关文法。你给出的文法是歧义的吗？为什么？

解：下面是产生A的一个CFG:

S?UV|AB U?aUb|? V?cV|? A?aA|? B?bUc|?

这个CFG是歧义的，因为字符串abc有如下两种不同的最左派生： S?UV?aUbV?abV?abcV?abc S?AB?aAV?aV?abVc?abc

2.11 给出识别2.10中语言A的下推自动机的非形式描述。 解：其非形式描述为：

此PDA有两个非确定性的分支：一个分支先读a，并且每读一个a将一个a推入栈中，当碰到b时，每读一个b从栈中弹出一个a，若没有a可弹出则拒绝，最后读c且不改变栈中的内容，若此时栈为空则接受。另一个分支也是先读a，但不改变栈中内容，当碰到b时，每读一个b将一个b推入栈中，再读c, 每读一个c从栈中弹出一个b，若没有a可弹出则拒绝，若c读完后栈为空则接受。开始时，读输入串的字符，非确定性的选择一个分支运行，若有一个分支接受则接受，否则拒绝。

2.14 设有上下文无关文法G:

S?TT|U U?0U00|# T?0T|T0|#

a. 用普通的语言描述L(G)。 b. 证明L(G)不是正则的。

解： a. A={0i#0j#0k | i, j, k?0}?{0i#02i | i?0}。

b. 取s=0#0, 则对于任意划分s=xyz(|xy|?p, |y|>0), xynz=0#0?A, 所以不是正则的。

p

2p

p+i

2p

2.15 用定理2.6中给出的过程，把下述CFG转换成等价的乔姆斯基范式文法。

A?BAB|B|? B?00|?

解：添加新起始变元S0, 去掉B??

S0?A S0?A A?BAB|B|? A?BAB|AB|BA|B|? B?00|? B?00

去掉A??, 去掉A?B S0?A S0?A A?BAB|AB|BA|B|BB A?BAB|AB|BA|00|BB B?00 B?00

去掉S0?A, 添加新变元 S0?BAB|AB|BA|00|BB S0?VB|AB|BA|UU|BB A?BAB|AB|BA|00|BB A?VB|AB|BA|UU|BB B?00 B?UU V?BA U?0

2.x 先说明如何把正则表达式直接转换成等价得上下文无关文法，然后利用问题xxx的结果，给出每一个正则语言都是上下文无关文法的一个证明。 解：设有正则表达式T，将其转化为上下文无关文法。 1) 首先添加S?T，且令S为起始变元。 2) 根据T的不同形式，按如下方式添加规则

①． 若T＝a??， 则在规则集中添加T?a, ②． 若T＝?， 则在规则集中添加T??, ③． 若T＝?， 则在规则集中添加T?T， ④． 若T＝A?B， 则在规则集中添加T?A|B， ⑤． 若T＝A·B, 则在规则集中添加T?AB， ⑥． 若T＝A*, 则在规则集中添加T?A,和A?AA|?

3) 若有新添加的变元，则根据其所对应的表达式转第2步，直到没有新的变元出现。

下面来证明每一个正则语言都是上下文无关的 由正则语言与正则表达式的等价性可知：对于一个正则语言都存在一个描述他的正则表达式，由前述讨论可知，这个正则表达式可转换为一个与之等价的上下文无关的文法。因此，此正则语言能由这个上下文无关文法产生。所以正则语言是上下文无关的。

2.18 a. 设C是上下文无关语言，R是正则语言。证明语言C?R是上下文无关的。

b． 利用a证明语言

A={w | w?{a,b,c}*, 且含有数目相同的a,b,c}

证明：a. 设P=(Q1,?,?,?1,q1,F1)是一个识别C的PDA，N=(Q2,?,?2,q2,F2)是识别R的一台NFA。下面构造识别C?R的PDA如下S=(Q,?,?,?,q0,F):

1) Q=Q1×Q2, 是状态集， 2) q0=(q1,q2)是起始状态， 3) F= F1×F2, 是接受状态集，

4) ?是转移函数，满足对任意q?Q1,r?Q2,a???,b???,

?((q,r),a,b)={((q’,r’),c) | q’??1(q,a), (r’,c)??2(r,a,b)}.

***nnn

b. A?abc={abc|n?0}, 若A是上下文无关的，则由a中命题知{anbncn|n?0}也是上下文无关的，矛盾。

2.26 证明：设G是一个Chomsky范式CFG，则对任一长度?2的字符串w?L(G), w的任何派生恰好有2n－1步。

证明：(用数学归纳法)当n=2时，对于Chomsky范式CFG，长度为2的字符串必由3步派生，此时命题为真。

假设当2?n?k时命题为真。当n=k+1时，对于长度为k+1的字符串s=s1s2?sk+1，存在S0的一个直接派生S0?AB，使得A产生子串s1s2?sp，B产生子串sp+1sp+2?sk+1，其中1?p?k+1。由归纳假设，A产生子串s1s2?sp需要2p-1步派生，而B产生子串sp+1sp+2?sk+1需要2(k+1-p)-1步派生。因此，S0产生字符串s共需2(k+1)-1步派生。即当n=k+1时命题亦真。 因此，由G产生长度为n?2的字符串需要2n-1派生。

2.30 用泵引理证明下述语言不是上下文无关的：

nnnn

a. {0101| n?0}

假设语言上下文无关，设p为泵长度，取S=0p1p0p1p.由泵引理知，S可以划分为uvxyz且满足泵引理条件。考察子串vxy,首先，它一定横跨S的中点，否则，若vxy位于S的前半段，由于|vxy|?p, 则uv2xy2z中1将是后半段字符串的第一个字符，即不可能是0n1n0n1n的形式。同理，vxy也不可能位于S后半段的位置上。但是,若vxy跨越S的中点时，将S抽取成uxz，它形如0p1i0j1p,i，j不可能都为p，即uxz不可能是0n1n0n1n的形式。

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

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

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

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

此，uv2xy2z不在该语言中。

22

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

也有uv2xy2z不在该语言中。

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

假设该语言上下文无关，设p为泵长度，取S=0p1p#0p1p, 由泵引理知，S可以划分为uvxyz且满足泵引理条件。显然，v,y中不包含#，不然抽取后的S=uxz中将不含#从而不在该语言中。 子串vxy不能落在#的左侧，否则uv2xy2z中#左侧的字符串长度将大于右边。 子串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}

假设该语言上下文无关，设p为泵长度，取S=apbp#apbp, 由泵引理知，S可以划分为uvxyz且满足泵引理条件。显然，v,y中不包含#，不然抽取后的S=uxz中将不含#从而不在该语言中。 子串vxy不能落在#的左侧，否则uv2xy2z中#左侧的字符串长度将大于右边。 子串vxy不能落在#的右侧，否则uxz中#左侧的字符串长度也会大于右边。

于是vxy跨越#两侧.此时，S经抽取成uxz后，具有apbi#ajbp的形式，其中，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。

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

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

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

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

b

层数?n的结点个数?2－1)，从而τ的由分支点组成的子树的高度大于等于R b+1。τ有一条路径上分支点(变元)个数?b+1。由鸽巢原理：必有某个变元R在该路径上出现至少两次。不妨假设R出现在路径上最下面的b+1个变

R 元中。

按上图所示，将S划分为uvxyz，在每一个R的下面有一棵子树，它产生S的一部分。上面的R有一

z vxy，u v x y 棵较大的子树，产生下面的R有一棵较大的子树，产生x，由于这两棵子树由同一个变元产生，

因而可以相互替换。这里采用如下操作：反复用较大子树去替换较小子树，则我们得到对于任意n>1, uv nxy nz?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。模拟过程使用深度搜索。

3) 需要一步 整个判定过程需要时间小于 (n-2)(1+n)=n2-n-2。运行时间为O(n2)。所以UNARY-PRIME?P。

7.8 令CONNECTED＝｛|G是连通的无向图｝。分析4.3.2节给出的算法，证明此语言属于P。 证明：判定CONNECTED的TM M的一个高水平描述： M=“输入是图G的编码：

1)选择G的第一个顶点，并作标记。

2)重复步骤(3)，直到没有新的顶点可以作标记。

3)对于G的每一个顶点，如果存在一条边，将其连到一个已作标记的顶点，则标记该顶

点。

4)扫描G的所有顶点，确定它们是否都已作了标记，如果是，则接受，否则拒绝。”

分析该算法的执行，步骤1)执行一次。一个n个顶点连通的无向图最多有n(n-1)/2条边，所以每次执行步骤3，运行时间是O(n2)。为标记所有的n个顶点，步骤3至多需要执行n次。所以用于标记的总的运行时间是O(n3)。步骤4需要执行n步。

该算法的总步数1+ O(n3)+n即为O(n3),从而有该语言属于P。

7.9 无向图中的三角形是一个3-团。证明TRIANGLE?P。其中 TRIANGLE＝{|G包含3-团} 证明思路：采用相邻矩阵的形式存储图，有n个结点的无向图G存储在矩阵Rn×n中，并且满足：R[i,i]=0, R[i,j]=1(当结点i和结点j之间有一条边)，R[i,j]=∞(当结点i和结点j之间不存在边)。从矩阵的第一行开始逐行扫描矩阵各行，在每一行中找两个为1的元素，假设当前扫描到第i行,若R[i,j]=1且 R[i,k]=1，则检查矩阵中 R[j,k]是否为1，若成立则接受，否则继续搜索。 证明：以算法D实现这一思路。 D=“对输入

1）计算R的结点数n。若n≤2，则拒绝。否则转2） 2）For i=1 to n

3） For j=i+1 to n 4） 若R[i,j]=1 则 5） For k=j+1 to n

6） 若R[i,k]=1 则检查矩阵中R[j,k]是否为1，若是则接受 7）若i,j,k同时为n，则拒绝。”

分析D，每一步都是在多项式时间内运行，步骤2最多运行n次，步骤2每运行一次步骤3最多运行n-i次,步骤3每运行一次步骤4最多运行n-j次。所以总计D执行O(n3)步。 7.11

证明：构造NTM如下： N=“对于输入，

1) 比较G与H节点数，若不相同，则拒绝。 2) 非确定地对G的节点进行重排。

3) 若G和H完全相同，则接受。否则拒绝”

N有n！个计算分支，每个长度为n，则此NTM有多项式时间，所以ISO∈NP。

问题

7.12 证明MODEXP?P。

设二进制整数b= kmkm-1…k1k0，则b=k020+k121+k222+…+km2m(ki =0,1)。构造判定MODEXP的图灵机如下： M=“对于输入，a,b,c,p为二进制整数，

(1) 以k0,k1,…,kn记b的从低位到高位的1至n+1位。 (2) 令d0=a，对于i=1,2,…,n计算di=di-1×di-1 mod p。

(3) 对于i=0,1,…,n，若ki=1，则令ci=di；若ki=0，则令ci=1。 (4) 计算e=c0×c1×…×cn mod p。

(5) 若e=c mod p，则接受，否则拒绝。”

设对于两个n位二进制整数，相乘再模一个至多n位的二进制整数，需要运行的时间为T。则第二步的时间为nT，第四步为nT，所以总的运行时间为O(nT)。这意味着MODEXP∈P。

7.14 证明P在星号运算下封闭。

证明：设M为判定A的时间f(n)图灵机，不妨设f(n)?n。设计如下TM： D=“对于输入y=y1y2…yn，

1) 若y=ε，则接受；

2) 对于i,j＝1,2,…,n重复(3)。

3) 在yiyi+1…yj上运行M。若接受，则令T(i, j)=“yes”。 4) 重复下面步骤直到表T不再改变。 5) 对于i,j＝1,2,…,n重复下面步骤。

6) 若T(i,j)=“yes”，转(5)。否则继续。

7) 对于k = i,i+1,…,j-1, 若T(i,k)=T(k+1,j)=“yes”,则令T(i,j)=“yes”。 8) 若T(1, n)=yes，则接受；否则拒绝。 运行时间：设O(n2f(n))+O(n3)＝O(n2f(n))。

7.15 证明NP在星号运算下封闭。

证明：设M为判定A的时间f(n)非确定图灵机，不妨设f(n)?n。设计如下NTM： D=“对于输入y=y1y2…yn，

1) 若y=ε，则接受；

2) 非确定地选择y的一个划分y=x1x2…xk，其中是x1,x2,…,xk字符串。 3) 对于i=1,2,…,k，重复下一步骤：

4) 在xi上运行M，若M拒绝，则拒绝。 5) 若都接受，则接受。”

以下略。若有兴趣讨论，可与刘庆晖(qhliu@bit.edu.cn)联系。

第四章

4.2 考虑DFA和正则表达式是否等价的问题。将这个问题表示为一个语言并证明它可判定。 解：设EQD-R={|A是DFA,B是正则表达式，L(A)=L(B)}。构造如下TM， 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是可判定的。 解：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的接受状态集。和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}。 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)即为所求语言。

第五章

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) 检测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??

?#?并且第一张骨牌改为?。 ??##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的规约函数:

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