计算理论答案汇总.docx

第一章
练习
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
q3
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为：

a b
q1
q2
q3
q4
q1 q2
q3 q4
q2 q1
q3 q4
3） q2是起始状态
4） F2={q1,q4}

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

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

1.6 画出识别下述语言的DFA的状态图。
a){w | w从1开始以0结束}

0
0
1
1
1
0,1
0

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

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

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

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

或

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

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

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

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

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

k) {ε,0}
0
0,1
0,1
1

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

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

1.7 给出识别下述语言的NFA，且要求符合规定的状态数。
0
0
0,1
a. {w | w以00结束}，三个状态

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

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

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

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

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

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的补集。

但是由于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属于Σ。

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

N1: N:

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

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

a)， b)，

解：a), b)
a
a
b
1
23
b
123
Æ
a
b
a,b
a,b
a
b
1
2
b
12
Æ
a
a,b

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} eÈΣÈΣΣÈΣΣΣÈΣΣΣΣÈΣΣΣΣΣ.
h. {w | w是除11和111以外的任何字符} 0Σ*È10Σ*È110Σ*È111ΣΣ*.
i. {w | w的奇位置均为1} (1Σ)*( eÈ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. (eÈa)b 成员：b，ab 非成员：a，bb
h. (aÈbaÈbb) Σ* 成员：a，bb 非成员：e，b

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

b
a
b
1
2
a

a), b),

解: a) a*b(aÈba*b)*
b) eÈ(aÈb)a*b[(aaÈabÈb)a*b]*(aÈe).
(注：答案不唯一)

1.29利用泵引理证明下述语言不是正则的。
a. A1={0n1n2n | n³0}。
证明：假设A1是正则的。设p是泵引理给出的关于A1的泵长度。
令S=0p1p2p,
∵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=apbapbapb,
∵S是A2的一个成员且S的长度大于p，所以泵引理保证S可被分成3段S=xyz且满足泵引理的3个条件。根据条件3，y中只含a，所以xyyz中第一个a的个数将比后两个a的个数多，故xyyz不是A2的成员。违反泵引理的条件1，矛盾。
∴A2不是正则的。
c. A3={a2n | n³0}.(在这里，a2n表示一串2n个a .)
证明：假设A3是正则的。设p是泵引理给出的关于A3的泵长度。
令S= a2p，
∵S是A2的一个成员且S的长度大于p，所以泵引理保证S可被分成3段S=xyz且满足泵引理的3个条件。即对任意的i³0，xyiz都应在A3中，且xyiz与xyi+1z的长度都应是2的幂. 而且xyi+1z的长度应是xyiz的长度的2n倍(n³1)。于是可以选择足够大的i，使得|xyiz|=2n>p. 但是|xyi+1z|-|xyiz|=|y|£p. 即|xyi+1z|<2n+1, 矛盾。
∴A3不是正则的。

1.30下面“证明”0*1*不是正则语言，指出这个“证明”中的错误。(因为0*1*是正则的，所以一定错误。) 采用反证法证明。假设0*1*是正则的。令P是泵引定理给出的关于0*1*的泵长度。取S为字符串0p1p。S是0*1*的一个成员，但是例2.38已证明S不能被抽取。于是得到矛盾，所以0*1*不是正则的。
解：在例2.38中的语言是{0n1n | n³0}，取S为字符串0p1p，S确实不能被抽取；但针对语言0*1*，S是能被抽取的。将S分成三段S=xyz，由泵引理的条件3，y仅包含0，而xyiz属于语言0*1*，即S能被抽取，故题设中的“证明”不正确。

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

T1 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对输入串e, 输出：e, 状态序列：q1。

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
q3
q1/0
q2/1

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

1.46 证明：
a) 假设{0n1m0n|m,n≥0}是正则的，p是由泵引理给出的泵长度。取s＝0p1q0p，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=0p1q0p，显然s是一个回文且长度大于p。由泵引理条件3知|xy|≤p，故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.

0
0
0
0
0
1
,
0
1
0
,
…
,
,
1
1
1
S3=
1.32 令

å3包括所有高度为3的0和1的列向量。å3上的字符串给出三行0和1的字符串。把每一行看作一个二进制数，令
B={ wÎå3* | w最下面一行等于上面两行的和}
例如，
, 而
ÎB
ÏB
0
0
1
1
0
0
1
1
0
0
0
1
1
0
1

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

0
0
0
0
0
1
0
1
0
0
1
1
1
0
0
1
0
1
1
1
0
1
1
1
q0
{q0}
Æ
Æ
{q0}
Æ
{q0}
{q1}
Æ
q1
Æ
{q0}
{q1}
Æ
{q1}
Æ
Æ
{q1}
F={q0}
q0
q1
0
0
1
1
1
0
1
0
1
1
0
1
0
0
0
1
1
1
1
0
0
0
1
0
,
,
,
,

状态图为：

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

,
,
,
S2=
0
0
0
1
1
1
1
0
1.33 令

S2包含所有高度为2的0和1的列。S2上的字符串给出两行0和1的字符串。把每一行看作一个二进制数，令
C={ wÎå2* | w下面一行等于上面一行的3倍 }。
证明C是正则的。可以假设已知问题2.24中的结果。
q0
q1
q2
0
0
1
1
1
1
0
0
0
1
1
0
证明：如下的NFA识别CR：其中q0状态表示上一次运算的进位为0，

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

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

的数的3倍余0,1,2的情况。
,
,
,
S2=
0
0
0
1
1
1
1
0

1.34令

S2包含所有高度为2的0和1的列。S2上的字符串给出两行0和1的字符串。把每一行看作一个二进制数，令
D={ wÎå2* | w上一行大于下一行 }。
证明D是正则的。
证明：由题设可设计自动机M=(Q, Σ, δ, q, F)，其中Q={q1,q2}，F={q2},
转移函数与状态图为：

0
0
0
1
1
0
1
1
q1
{q1}
Æ
{q2}
{q1}
q2
{q2}
{q2}
{q2}
{q2}
q1
q2
0
0
1
1
0
1
1
0
1
1
0
0
1
0
,
,
,
,

1.35设∑2与问题2.26中的相同。把每一行看作0和1的字符串，令E={wÎå2* | w的下一行是上一行的反转}，证明E不是正则的。
1
0
p
0
1
p
证明：假设E是正则的，令p是有泵引理给出的泵长度。
1
0
选择字符串s= 。于是s能够被划分为xyz且满足泵引理的条件。
根据条件3，y仅能取包含 的部分，当添加一个y时，xyyz不属于E. 所以E不是正则的.
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：(正向读)
M=( Q, {0,1} , d , q0 , F ), 其中Q＝{0,1,2,…，n-1},
d( i,1)=2i+1 mod n, d( i,0 )=( 2i mod n), i=0,1,2,…，n-1,
起始状态为0, F＝{0}.
这里i表示当前数mod n余i.

下面的DFA识别CnR：(反向读)
M=( Q, {0,1} , d , q0 , F ), 其中Q＝{(i,j)|i,j=0,1,2,…，n-1},
d((i,j),1)=( 2i mod n, (2i+j)mod n ), d((i,j),0)=( 2i mod n, j ), i,j=0,1,2,…，n-1
起始状态为(1,0), F＝{ (i,0) | i=0,1,…，n-1}.
这里(i,j)表示当前数mod n余j, 而下一位所表示单位数mod n余i(例如，若读下一位将达到k位，则下一位所表示单位数为10k-1).
1.38 考虑一种叫做全路径NFA的新型有穷自动机。一台全路径NFA M是5元组 ( Q, å, d, q0, F). 如果M对xÎå*的每一个可能的计算都结束在F中的状态，则M接受x。注意，相反的，普通的NFA只需有一个计算结束在接受状态，就接受这个字符串。证明：全路径NFA识别正则语言。
证明：一个DFA一定是一个全路径NFA。所以下面只需证明，任意全路径NFA，都有一个与之等价的DFA。
设有一全路径NFA N=( Q, Σ, δ, q0, F)，构造一个新与N等价的全路径NFA
N1＝( Q1, Σ, δ1, q0, F), 其中Q1=QÈ{s}, sÏQ。对于任意qÎQ1, aÎΣε
δ(q,a)， q ¹ s, 且δ(q,a) ¹Æ;
δ1(q,a) = {s}, q ¹ s, 且δ(q,a) =Æ;
{s}, q=s.
现在来构造一个与全路径NFA N1等价的DFA M＝(Q2, Σ, δ2, q1, F2). 其中
1) Q2=Power(Q1), 即Q1的所有子集组成的集合(也即Q1的幂集)；
2) 定义函数E: Q2àQ2为：对任意RÎQ2, ；
3) q1=E(q0);
4) 对于任意的R属于Q2, a属于Σ, .
5) F2={ RÎQ2 | RÍF}。
综上所述，DFA等价于全路径NFA。

1.40如果存在字符串z使得xz=y,则称字符串x是字符串y的前缀。如果x是y的前缀且x≠y,则称x是y的真前缀。下面每小题定义一个语言A上的运算。证明：正则语言类在每个运算下封闭。
a) NOPREFIX(A)={ω∈A|ω的任意真前缀都不是A的元素}
b)NOEXTEND(A)={ ω∈A|ω不是A中任何字符串的真前缀}
证明：假设DFA M=( Q, Σ, δ, q0, F)识别语言A。
a) 构造NFA N1=( Q, Σ, δ1, q0, F)识别语言NOPREFIX(A)。其中，
对任意qÎF, a ÎΣe,
所以，即NOPREFIX(A)为正则语言，亦即正则语言类A在NOPREFIX(A)运算下封闭。█
b) 构造NFA N2=( Q, Σ, δ, q0, F2)识别语言NOEXTEND(A)。F2构造如下：
对M中的任一接受状态qi, 若存在一条从它出发到达某接受状态(含本身)的路径，则将状态qi改为非接受状态; 最后剩下的接受状态集记为F2. 所得的NFA N2即识别NOEXTEND(A)。所以，NOEXTEND(A)为正则语言，亦即正则语言类A在运算NOEXTEND(A)下封闭。█

0
1
0
1
1
0
1
1
0
0
1
10
0
01
1.48 证明：构造NFA N如下：

由于该NFA识别D，故D是正则语言。

1.50参见练习1.24中给出的有穷状态转换器的非形式定义。证明不存在FST对每一个输入w能够输出wR，其中输入和输出的字母表为{0,1}。
证明：假设存在一台FST对每个输入w能够输出wR。
则对于输入串w1 =100, w2=101.
该FST可分别输出w1R=001，w2R=101，于是对于它的起始状态和输入字符1，会输出1和0两个不同字符，这与FST是确定性有穷自动机相矛盾。
所以，不存在一台FST对每个输入w能够输出wR。

1.51
证明: 1) 自反性。即对任意字符串x，xºLx。这是因为对于每个字符串z均有xz和xz同时是或不是L的成员。
2) 对称性。即对任意字符串x和y, 若xºLy，则yºLx。这是因为若xºLy，则对于每个字符串z, xz和yz同时是或不是L的成员，那么yz和xz同时是或不是L的成员, 于是yºLx。
3) 传递性。即对任意字符串x,y和z, 若xºLy且yºLz，则xºLz。这是因为对任意字符串u, 由xºLy知xu和yu同时是或不是L的成员, 由yºLz知yu和zu同时是或不是L的成员, 所以xu和zu同时是或不是L的成员, 此即xºLz。
综上所述，ºL是自反的，对称的，传递的，所以是一个等价的关系。

1.53 令Σ={0，1，+，=}和
ADD={ x=y+z | x,y,z是二进制整数，且x是y与z的和}
证明ADD不是正则的。
证明：假设ADD是正则的。设P是泵引理给出的关于ADD的泵长度。令s为1P=10P-1+1P-1。于是s能够被划分成xyz，且满足泵引理的条件。根据条件3，y=1i, i>0. 所以xyyz为1P+i=10P-1+1P-1ÏADD。故ADD不是正则的。

1.54证明：语言F={aibjck | i,j,k³0且若i=1，则j=k}满足泵引理的3个条件，虽然它不是正则的。解释这个事实为什么与泵引理不矛盾。
证明：对任意正数p>1，设S是F中的一个成员且S的长度不小于p。
将S分成3段S=xyz。
(1) i=0，j=0. 此时S=ck (k>0)。
取x=e, y=c, z=ck-1. 则对任意i³0, xyizÎF。
(2) i=0，j>0. 此时S=bjck(j>0, k³0).
取x=e, y=b, z=bj-1ck. 则对任意i³0, xyizÎF。
(3) i=1. 此时S=abjck(j³0, k³0).
取x=e, y=a, z=bjck. 则对任意i³0, xyizÎF。
(4) i=2. 此时S= a2bjck(j³0, k³0).
取x=e, y=a2, z=bjck. 则对任意i³0, xyizÎF。
(5) i>2. 此时S= aibjck(i³3, j³0, k³0).
取x=e, y=a, z=ai-1bjck. 则对任意i³0, xyizÎF。
综上所述，语言F满足泵引理的3个条件。这一事实不与泵引理矛盾是因为泵引理是正则语言的必要不充分条件。

1.55 求最小泵长度。
a. 0001*的最小泵长度为4.
因为对任何s 若|s|=3则s只含有0，不能被抽取。
若|s|≥4时，把s划分为x=000 y=1 z为其余部分，则xyizÎ0001*。
b. 0*1*最小泵长度为1.
若|s|≥1时,S分两种情况：
1． S以0开头,令x=e, y=0, z为其余则xyizÎ0*1*.
2． S以1开头,令x=e, y=1, z为其余则xyizÎ0*1*.
c. (01)*最小泵长度为2.
若|s|≥2时,令x=e, y=01, z为其余, 则xyizÎ(01)*.
d. 01，其最小泵长度为3。
因为语言中只有有限个字符串时，任何一个字符串都不能被抽取。所以有限语言的泵长度为其最长字符串的长度加1。此时没有比泵长度长的字符串，前提假所以命题真。
e. e，其最小泵长度为1.
理由类似于d中所述。

2.39 证明：设对于每一个k>1，Ak={ w | w包含子串1k-1}Í{1}*，下面证明Ak能被一台k个状态的DFA识别，而不能被只有k－1个状态的DFA识别。
显然，Ak能被k个状态的DFA
M=({q1,q2,…,qk}, {1}, d, q1, {qk}).
识别, 其中d(qi,1)=qi+1(i=1,2,…,k-1), d(qk,1)=qk。
假设AK可以被只有k-1个状态的DFA　M1识别。
考虑这样一个输入串s=1k-1，设M识别s的状态序列是r1, r2,…rk,由于M的状态只有k-1个，根据鸽巢原理，r1,r2,…,rk中必有两个重复的状态，假设是ri=rj (0£i<j£k)，此时可知，字符串x=1j-i把M从ri带到了rj。由于ri,rj是同一个状态，所以去掉s中的x子串，M仍可识别s的剩余部分，即M识别1k-1-(j-i)，这与M1识别Ak相矛盾。故Ak不能被只有k-1个状态的DFA M识别。
所以，对于每一个k>1，存在AK，使得AK能被K个状态的DFA识别，而不能被只有k-1个状态的DFA识别。

第二章
2.1 略。
2.2 a. 利用语言A={ambncn | m,n³0}和A={anbncm | m,n³0}以及例3.20，证明上下文无关语言在交的运算下不封闭。
b. 利用(a)和DeMorgan律(定理1.10)，证明上下文无关语言在补运算下不封闭。
证明：a.先说明A,B均为上下文无关文法，对A构造CFG C1
S®aS|T|e
T®bTc|e
对B,构造CFG C2
S®Sc|R|e
R®aRb
由此知 A,B均为上下文无关语言。
但是由例3.20, A∩B={anbncn|n³0}不是上下文无关语言，所以上下文无关语言在交的运算下不封闭。
b.用反证法。假设CFL在补运算下封闭，则对于(a)中上下文无关语言A,B，,也为CFL，且CFL对并运算封闭，所以也为CFL，进而知道为CFL，由DeMorgan定律＝A∩B，由此A∩B是CFL,这与(a)的结论矛盾，所以CFL对补运算不封闭。

2.3 略。

2.4和2.5 给出产生下述语言的上下文无关文法和PDA，其中字母表S={0,1}。
e,1®e
1, e®1
0, e®e
e,1®e
e,1®e
a. {w | w至少含有3个1}
S→A1A1A1A
A→0A|1A|e

b. {w | w以相同的符号开始和结束}
1,e®1
1,e®e
0,e®e
0,e®0
1,1®e
0,0®e
S→0A0|1A1
A→0A|1A|e

1,e®e
0,e®e
1,e®e
0,e®e
c. {w | w的长度为奇数}
S→0A|1A
A→0B|1B|e
B→0A|1A

d. {w | w的长度为奇数且正中间的符号为0}
S→0S0|1S1|0S1|1S0|0
1,e®0
0,e®e
0,e®0
1,0®e
0,0®e
e,e®$
e,$®e

1,e®1
e,1®e
0,e®0
e,1®e
e,e®$
e,$®e
1,0®e
0,1®e
e. {w | w中1比0多}
S→A1A
A→0A1|1A0|1A|AA|e

f. {w | w=wR}
S→0S0|1S1|1|0
1,e®1
0,e®e
0,e®0
1,1®e
0,0®e
e,e®$
e,$®e
1,e®e
e,e®e

g. 空集
S→S

2.6 给出产生下述语言的上下文无关文法：
a． 字母表{a,b}上a的个数是b的个数的两倍的所有字符串组成的集合。
S→bSaSaS|aSbSaS|aSaSbS|e
b．语言{anbn|n³0}的补集。见问题3.25中的CFG:
S→aSb|bY|Ta
T→aT|bT|e
c．{w#x | w, xÎ{0,1}*且wR是x的子串}。
S→UV
U→0U0|1U1|W
W→W1|W0|#
V→0V|1V|e
d．{x1#x2#¼#xk|k³1, 每一个xiÎ{a,b}* , 且存在i和j使得xi＝xjR}。
S→UVW
U→A|e
A→aA|bA|#A|#
V→aVa|bVb|#B|#
B→aB|bB|#B|#
W→B|e

2.8 证