%
计算理论习题解答
练习
图给出两台DFA M1和M2的状态图. 回答下述有关问题.
a. M1的起始状态是q1 b. M1的接受状态集是{q2} c. M2的起始状态是q1
d. M2的接受状态集是｛q1，q4｝
e. { f. 对输入aabb,M1经过的状态序列是q1，q2，q3，q1，q1 g. M1接受字符串aabb吗否 h. M2接受字符串ε吗是
给出练习中画出的机器M1和M2的形式描述.
M1=(Q1,Σ,δ1,q1,F1) 其中 1） Q1={q1,q2,q3,}; 2） Σ={a,b};
3） ] 4） δ1为：
q1 q2 q3 a b q2 q1 q3 q3 … q2 q1 5） q1是起始状态 6） F1={q2}
M2=(Q2,Σ,δ2,q2,F2) 其中 1） Q2={q1,q2,q3,q4}; 2） Σ={a,b}; 3）δ2为：
$ a b q1 q2 q3 q4 — q2 q1 q3 q4 q1 q2 q3 q4 3） q2是起始状态 4） F2={q1,q4}
DFA M的形式描述为 ( {q1，q2，q3，q4，q5}，{u,d},δ,q3，{q3}),其中δ在表2-3中给出。试画出此机器的状态图。
—
d u . d q2 q3 ^d q4 u d q5 u d
u
画出识别下述语言的DFA的状态图。
a){w | w从1开始以0结束} —
#
1 1 0 0,1 0
0
%
b){w | w至少有3个1}
|
0 0 0 1 0,1 1
c) {w | w含有子串0101} 1 0
)
…0 1 0 1 0, 1
d) {w | w的长度不小于3，且第三个符号为0}
0,1 0
：
, 0,1 0
0,
e) {w | w从0开始且为奇长度，或从1开始且为偶长度}
-
0 0 或 0,0, 0,） 1
0,
f) {w | w不含子串110}
。
0,0
g) {w | w的长度不超过5} ·
1 1 0 0,0,1 0 ^ 0,0,0,0,0,
h){w | w是除11和111以外的任何字符}
1 1 1 0 0 0 ]
。
i){w | w的奇位置均为1}
1
—
0 0,
0,
j) {w | w至少含有2个0，且至多含有1个1} |
1
0 0
1 1 0,
\\
0 1 0 1
—
0
k) {ε,0} 、 0 0,
1
l) {w | w含有偶数个0，或恰好两个1}
1 1 1
/
1 0 0 0 0 0 | 0 0 1 1 1 {
m) 空集 n) 除空串外的所有字符串 《 0,0,
给出识别下述语言的NFA，且要求符合规定的状态数。
a. {w | w以00结束}，三个状态 0,
0 0
b. 语言｛w | w含有子串0101，即对某个x和y，w=x0101y｝，5个状态.
0,0,
《{
1 0 1
c. 语言｛w | w含有偶数个0或恰好两个1｝，6个状态。
%
1 0 0 1 #1 0 1 0
***
d. 语言｛0｝，2个状态。
【 e. 语言0100，3个状态。
]
0 f. 语言{ε}，1个状态。
|
0 0
*
g. 语言0，1个状态。
0
证明每一台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)若rnF 则ωB;
2)若rnF,则rnQ-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交换接受与非接受状态构造而成。
给出一个反例，说明下述构造不能证明定理，即正则语言类在星号运算下封闭。设N=（Q1,Σ,δ1,q1,F1）
*
识别A1。如下构造N=（Q1,Σ,δ1,q1,F1）。N应该识别A1。
a. N的状态集是N1的状态集。
b. N的起始状态是N1的起始状态相同。
c. | d. F=｛q1｝∪F1。F的接受状态是原来的接受状态加上它的起始状态。 e. 定义δ如下：对每一个q属于Q和每一个a属于Σ。
若qF1 或 a1(q,a), (q,a)1(q,a){q1}, 若qF1 且 a
*
解：设N1识别语言A={至少含有一个1}，其中输入字母表为{0，1}，可知A={空串或至少含有一个1}。 a 0,0,N1: N:
a,1 1 )
b 2 ?
***
按上述规定构造N的状态图如上。可以看出L(N)={0,1}不等于A. 所以如此构造的N不一定识别A.
使用定理中给出的构造，把下图中的两台非确定型有穷自动机转换成等价的确定型有穷自动机。
。 0, 1 1 2 a)， b)， a a a,
3 ！ 解：a), b) —
.
1 b b a 12 a,1 b {a a 12a
b 23 b
a ） a,a,
给出生成练习中语言的正则表达式。(注: 答案不唯一)
*
a. {w | w从1开始以0结束} 1Σ0.
****
b. {w | w至少有3个1} Σ1Σ1Σ1Σ.
c. 、
**
d. {w | w含有子串0101} Σ0101Σ.
e. f. g. h. i. j. k. {w | w的长度不小于3，且第三个符号为0} ΣΣ0Σ.
**
{w | w从0开始且为奇长度，或从1开始且为偶长度} 0(ΣΣ)1Σ(ΣΣ).
**
{w | w不含子串110} (010)1. {w | w的长度不超过5} ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ.
****
{w | w是除11和111以外的任何字符} 0Σ10Σ110Σ111ΣΣ.
*
{w | w的奇位置均为1} (1Σ)( 1).
**
{w | w至少含有2个0，且至多含有1个1} 0(00010001100) 0.
*
l. % m. {ε,0}. ε0.
*******
n. {w | w含有偶数个0，或恰好两个1} (1010)101010. o. 空集. .
*
p. 除空串外的所有字符串ΣΣ.
对下述每一个语言，给出4个字符串，2个是这个语言的成员，2个不是这个语言的成员。这里假设字母表Σ={a,b}.
^
a. ab 成员：ab，aab 非成员：aba，ba
*
b. a(ba) 成员：ab，abab 非成员：abb，aa
**
c. ab 成员：aaa，bbb 非成员：ab，ba
*
d. (aaa) 成员：aaa，aaaaaa 非成员：a，aa
****
e.ΣaΣbΣaΣ成员：aba，aaba 非成员：aa，abb f. ababab 成员：aba，bab 非成员：a，b g. (a)b 成员：b，ab 非成员：a，bb
*
h. (ababb) Σ 成员：a，bb 非成员：，b
#
**
使用引理中叙述的过程，把图2-38中的有穷自动机转换成正则表达式。
a, : 2 a a a), b),
b b a （ 1 b
b 3
***
解: a) ab(abab)
#
b) (ab)ab[(aaab(注：答案不唯一)
*
a
b)ab](a
**
).
利用泵引理证明下述语言不是正则的。 a. A1={012| n0}。
证明：假设A1是正则的。设p是泵引理给出的关于A1的泵长度。
nnn
令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,
∵S是A2的一个成员且S的长度大于p，所以泵引理保证S可被分成3段S=xyz且满足泵引理的3个条件。根据条件3，y中只含a，所以xyyz中第一个a的个数将比后两个a的个数多，故xyyz不是A2的成员。违反泵引理的条件1，矛盾。 ∴A2不是正则的。
c. A3={a | n0}.(在这里，a表示一串2个a .)
…
ppp
ppp
2
n
2
nn
证明：假设A3是正则的。设p是泵引理给出的关于A3的泵长度。
令S= a，
∵S是A2的一个成员且S的长度大于p，所以泵引理保证S可被分成3段S=xyz且满足泵引理的3
iii+1i+1
个条件。即对任意的i0，xyz都应在A3中，且xyz与xyz的长度都应是2的幂. 而且xyz的长度应是xyz的长度的2倍(n1)。于是可以选择足够大的i，使得|xyz|=2>p. 但是|xyz|-|xyz|=|y|p. 即|xyz|<2, 矛盾。 ∴A3不是正则的。
****
下面“证明”01不是正则语言，指出这个“证明”中的错误。(因为01是正则的，所以一定错误。) 采用反证法证明。假设01是正则的。令P是泵引定理给出的关于01的泵长度。取S为字符串01。S是01的一个成员，但是例已证明S不能被抽取。于是得到矛盾，所以01不是正则的。
解：在例中的语言是{01 | n
nn
**
**
**
pp
**
i+1
i
i+1
n+1
i
n
i
n
2p
0}，取S为字符串01，S确实不能被抽取；但针对语言01，S是
i
**
pp
**
能被抽取的。将S分成三段S=xyz，由泵引理的条件3，y仅包含0，而xyz属于语言01，即S能
被抽取，故题设中的“证明”不正确。
有穷状态转换器(FST)是确定性有穷自动机的一种类型。它的输出是一个字符串，而不仅仅是接受或拒绝。图2—39是两台有穷状态状态转换器T1和T2的状态图。 # 0/q1
0 1/ a/2/a/b/ 。 q1 q2
0/q3 b/~ q2
T1 T2
&
FST的每一个转移用两个符号标记，一个指明该转移的输入符号，另一个指明输出符号。两个符号之间用斜杠“/”把它们分开。在T1中，从q1到q2的转移有输入符号2和输出符号1。某些转移可能有多对输入-输出，比如T1中从q1到它自身的转移。FST在对输入串w计算时，从起始状态开始，一个接一个地取输入符号w1wn，并且比照输入标记和符号序列w1wn=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。
'
给出有穷状态转换器的形式定义。
解：有穷状态转换器FST是一个五元组(Q,Σ,Г,δ,q0)
1) Q是一个由穷集合，叫做状态集
2) Σ是一个由穷集合，叫做输入字母表 3) Г是一个由穷集合，叫做输出字母表 4) δ：Q×ΣQ×Г是转移函数 5) q0是起始状态
。
FST计算的形式定义：
M=(Q,Σ,Г,δ,q0)是一台由穷状态转换器，w=w1w2wn是输入字母表上的一个字符串。若存在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.
利用你给练习的答案，给出练习中画出的机器T1和T2的形式描述。 解：有穷状态转换器T1的形式描述为：
T1=({q1, q2 }, {0，1，2},δ, q1, {0,1}) ~
其中转移函数为：
q1 q2 0 q1/0 q1/0 1 q1/0 q2/1 2 | q2/1 q/1 2有穷状态转换器T2的形式描述为：
T2=({{q1, q2, q3}, {a, b},δ, q1, {0,1})
其中转移函数为：
！ a q2/1 q3/1 q1/0 b q3/1 ，q1 q2 q3 q1/0 q2/1
给出一台具有下述行为的FST的状态图。它的输入、输出字母表都是{0,1}。它输出的字符串与输入的字符串偶数为相同、奇数位相反。例如，对于输入0000111，它应该输出1010010。 解：
1/
0
q1 q2
~
1/1
证明：
a) 假设{010|m,n≥0}是正则的，p是由泵引理给出的泵长度。取s＝010，q>0。由泵引理条件3知，|xy|≤p，故y一定由0组成，从而字符串xyyz中1前后0的数目不同，即xyyz不属于该语言，这与泵引理矛盾。所以该语言不是正则的。
nnnn
b) 假设{01|n≥0}的补集是正则的，则根据正则语言在补运算下封闭可得{01|n≥0}是正则的，这与已
知矛盾，故假设不成立。所以该语言不是正则的。
mn**nnnn
记c={01|m≠n}，┐c为c的补集，┐c∩01={01|n≥0}，已知{01|n≥0}不是正则的。若 ┐c是
****
正则的，由于01是正则的，那么┐c∩01也应为正则的。这与已知矛盾，所以 ┐c不是正则的。由正则语言在补运算下的封闭性可知c也不是正则的。
**
c) {w | w{0,1}不是一个回文}的补集是{w | w{0,1}是一个回文}，设其是正则的，令p是由泵引理
给出的泵长度。取字符串s=010，显然s是一个回文且长度大于p。由泵引理条件3知|xy|≤p，故y只能由0组成。而xyyz不再是一个回文，这与泵引理矛盾。所以{w | w{0,1}是一个回文}不是正
*
则的。由正则语言在补运算下的封闭性可知{w | w{0,1}不是一个回文}也不是正则的。
RR
对于任意的字符串w=w1w2…wn，w的反转是按相反的顺序排列w得到的字符串，记作w，即w=wn…w2w1。
RR R
对于任意的语言A，记 A={w| A}证明：如果A是正则的，则A也是正则的。 】
证明：
R
因为A是正则语言，所以可以用NFA来表示该语言，现在来构造A的NFA，将NFA A中的接受态变为中间态，起始态变为接受态，再添加一新的起始态，并用ε箭头连接至原来的接受态，其它所有的箭头反向。
R
经过变换后得到NFA变成描述A的NFA. 令 0 0 0 1
1 0 , … , 1 | …,3
：
nmnpqp
pqp
*
0 0
1
0 1
包括所有高度为3的0和1的列向量。3上的字符串给出三行0和1的字符串。把每一行看作一个二进制数，令
*
B={ w3 | w最下面一行等于上面两行的和}
例如，
3
…
证明B是正则的。
证明：由题设B的定义可知，w上面两行之和减去下面一行结果为零，由此可设计NFA M (Q, Σ, δ, q0, F)，其中=3。Q={q0,q1}。q0状态表示上一次运算的进位为0，q1状态表示上一次运算的进位为1。 δ由下表给出：
: 0 0 0 1 1 1 1 & 0 1 0 0 0 1 1 % 0 1 0 1 0 0 1 q0 &0 1
0 0 1 0 1 … 0 ,
0 0 1 1 0 ~ 1 0 【 {q0} 1 {q0} {q1} {q0} {q1} 1 {q0} {q1} > q1 F={q0}
状态图为： 1 1 0 0 , 0 , 0
* 1 0
$
{q1} 1 0 —q0 0 0 1 R
R
q1 1 1 0 1 , < : 1
0 1 0 所以可知自动机M识别的是语言B，因此B是正则的。由题2-24的结论可知B也是正则的。
令
0 , 0 1 1 , ,
2
：
}
1 0 1 包含所有高度为2的0和1的列。2上的字符串给出两行0和1的字符串。把每一行看作一个二进制
数，令
*
C={ w2 | w下面一行等于上面一行的3倍 }。
证明C是正则的。可以假设已知问题中的结果。
R
证明：如下的NFA识别C：其中q0状态表示上一次运算的进位为0，
1 1
1 0 ]
2
0 q0 q1 q2 1 ；0 0 1 1
?
q1状态表示上一次运算的进位为1, q2状态表示上一次运算的进位为2。
如下的NFA识别C：其中状态q0,q1,q2分别表示目前读到的下面的数减上面 0 0 1 0 ! 1 q0 q1 q2 0 1 | 1 —
1 0 的数的3倍余0,1,2的情况。 令 0 0 {
2
1 1 , , , ； 1 0 1
包含所有高度为2的0和1的列。2上的字符串给出两行0和1的字符串。把每一行看作一个二进制数，令
*
D={ w2 | w上一行大于下一行 }。
证明D是正则的。
证明：由题设可设计自动机M=(Q, Σ, δ, q, F)，其中Q={q1,q2}，F={q2}, 转移函数与状态图为： 2
0 } 0 ( {q1} {q2} 0 1 {q2} 1 0 {q2} {q2} 1 1 {q1} ]q1 q2
`
{q2} 0 , 1 0 1 q1 1 0 q2 0 , \" , { , 1 0 1 0 1
设∑2与问题中的相同。把每一行看作0和1的字符串，令E={w明E不是正则的。
证明：假设E是正则的，令p是有泵引理给出的泵长度。
*2
| w的下一行是上一行的反转}，证
p 1 选择字符串s= 。于是s能够被划分为xyz且满足泵引理的条件。
0 1
1
0
。
p
根据条件3，y仅能取包含 的部分，当添加一个y时，xyyz不属于E. 所以E不是正则的. 令Bn={ak | k是n的整数倍}。证明对于每一个n1, Bn是正则的。
·
证明：设字母表∑为{a}，则a是一正则表达式。所以，(a)也是正则表达式。由题意Bn=(a),即Bn可以用正则表达式表示。所以，Bn也是正则的。
令Cn={x | x是一个二进制数，且是n的整数倍}。证明对于每一个n1, Cn是正则的。 证明：下面的DFA识别Cn：(正向读)
M=( Q, {0,1} , , q0 , F ), 其中Q＝{0,1,2,…，n-1},
( i,1)=2i+1 mod n, ( i,0 )=( 2i mod n), i=0,1,2,…，n-1, 起始状态为0, F＝{0}.
这里i表示当前数mod n余i.
~
nn*n*
下面的DFA识别Cn：(反向读)
M=( Q, {0,1} , , q0 , F ), 其中Q＝{(i,j)|i,j=0,1,2,…，n-1},
((i,j),1)=( 2i mod n, (2i+j)mod n ), ((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位，
k-1
则下一位所表示单位数为10).
考虑一种叫做全路径NFA的新型有穷自动机。一台全路径NFA M是5元组 ( Q, , , 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}, sQ。对于任意qQ1, 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: Q2Q2为：对任意RQ2, E(R)1(r,)；
rR；
R
3) q1=E(q0);
4) 对于任意的R属于Q2, a属于Σ, 2(R,a)E1(r,a).
rR5) F2={ RQ2 | RF}。
综上所述，DFA等价于全路径NFA。
如果存在字符串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,a)},qQF,a;,qF; 对任意qF, a Σ, 1(q,a) ,qQ,a;所以，即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)下封闭。█
￥
证明：构造NFA N如下：
—
0 1 0 0 0 1 1 1 1 0 \"
…
01 0 10
由于该NFA识别D，故D是正则语言。
R
参见练习中给出的有穷状态转换器的非形式定义。证明不存在FST对每一个输入w能够输出w，其中输入和输出的字母表为{0,1}。
R
证明：假设存在一台FST对每个输入w能够输出w。
则对于输入串w1 =100, w2=101.
RR
该FST可分别输出w1=001，w2=101，于是对于它的起始状态和输入字符1，会输出1和0两个不同字符，这与FST是确定性有穷自动机相矛盾。 -
所以，不存在一台FST对每个输入w能够输出w。
证明: 1) 自反性。即对任意字符串x，x
的成员。
R
L
x。这是因为对于每个字符串z均有xz和xz同时是或不是L
2) 对称性。即对任意字符串x和y, 若xLy，则yLx。这是因为若xLy，则对于每个字符串z, xz和yz同时是或不是L的成员，那么yz和xz同时是或不是L的成员, 于是yLx。
3) 传递性。即对任意字符串x,y和z, 若xLy且yLz，则xLz。这是因为对任意字符串u, 由xLy知xu和yu同时是或不是L的成员, 由yLz知yu和zu同时是或不是L的成员, 所以xu和zu同时是或不是L的成员, 此即xLz。
综上所述，L是自反的，对称的，传递的，所以是一个等价的关系。 `
令Σ={0，1，+，=}和
ADD={ x=y+z | x,y,z是二进制整数，且x是y与z的和}
证明ADD不是正则的。
PP-1P-1
证明：假设ADD是正则的。设P是泵引理给出的关于ADD的泵长度。令s为1=10+1。于是s能够被划
iP+iP-1P-1
分成xyz，且满足泵引理的条件。根据条件3，y=1, i>0. 所以xyyz为1=10+1ADD。故ADD不是正则的。
ijk
证明：语言F={abc | i,j,k0且若i=1，则j=k}满足泵引理的3个条件，虽然它不是正则的。解释这个事实为什么与泵引理不矛盾。
证明：对任意正数p>1，设S是F中的一个成员且S的长度不小于p。
将S分成3段S=xyz。
(1) >
k
(2) i=0，j=0. 此时S=c(k>0)。
k-1i
取x=, y=c, z=c. 则对任意i0, xyzF。
jk
(3) i=0，j>0. 此时S=bc(j>0, k0).
j-1ki
取x=, y=b, z=bc. 则对任意i0, xyzF。
jk
(4) i=1. 此时S=abc(j0, k0).
jki
取x=, y=a, z=bc. 则对任意i0, xyzF。
2jk
(5) i=2. 此时S= abc(j0, k0).
2jki
(6) 取x=, y=a, z=bc. 则对任意i0, xyzF。
ijk
(7) i>2. 此时S= abc(i3, j0, k0). ^
取x=, y=a, z=abc. 则对任意i0, xyzF。
综上所述，语言F满足泵引理的3个条件。这一事实不与泵引理矛盾是因为泵引理是正则语言的必要不充分条件。
求最小泵长度。
*
a. 0001的最小泵长度为4.
因为对任何s 若|s|=3则s只含有0，不能被抽取。
i*
若|s|≥4时，把s划分为x=000 y=1 z为其余部分，则xyz0001。 **
b. 01最小泵长度为1.
, 若|s|≥1时,S分两种情况：
i**
1． S以0开头,令x=, y=0, z为其余则xyz01.
i**
2． S以1开头,令x=, y=1, z为其余则xyz01. *
c. (01)最小泵长度为2.
i*
若|s|≥2时,令x=, y=01, z为其余, 则xyz(01).
i-1jk
i
d. 01，其最小泵长度为3。
因为语言中只有有限个字符串时，任何一个字符串都不能被抽取。所以有限语言的泵长度为其最长字符串的长度加1。此时没有比泵长度长的字符串，前提假所以命题真。 e. ，其最小泵长度为1. 理由类似于d中所述。
(
证明：设对于每一个k>1，Ak={ w | w包含子串1}{1}，下面证明Ak能被一台k个状态的DFA识别，而不能被只有k－1个状态的DFA识别。
显然，Ak能被k个状态的DFA
M=({q1,q2,…,qk}, {1}, , q1, {qk}).
识别, 其中(qi,1)=qi+1(i=1,2,…,k-1), (qk,1)=qk。
假设AK可以被只有k-1个状态的DFA M1识别。
k-1
考虑这样一个输入串s=1，设M识别s的状态序列是r1, r2,…rk,由于M的状态只有k-1个，根据鸽
j-i
巢原理，r1,r2,…,rk中必有两个重复的状态，假设是ri=rj (0i ， k-1* 略。 mnnnnm 2.2 a. 利用语言A={abc | m,n0}和A={abc | m,n0}以及例，证明上下文无关语言在交的运算下不封闭。 b. 利用(a)和DeMorgan律(定理，证明上下文无关语言在补运算下不封闭。 证明：a.先说明A,B均为上下文无关文法，对A构造CFG C1 SaS|T| TbTc| 对B,构造CFG C2 { SSc|R| RaRb 由此知 A,B均为上下文无关语言。 nnn 但是由例, A∩B={abc|n0}不是上下文无关语言，所以上下文无关语言在交的运算下不封闭。 b.用反证法。假设CFL在补运算下封闭，则对于(a)中上下文无关语言A,B，A,B也为CFL，且CFL对并运算封闭，所以AB也为CFL，进而知道AB为CFL，由DeMorgan定律AB＝A∩B，由此A∩B是CFL,这与(a)的结论矛盾，所以CFL对补运算不封闭。 略。 , 和 给出产生下述语言的上下文无关文法和PDA，其中字母表={0,1}。 a. {w | w至少含有3个1} 0, 1, ,1,1,1 S→A1A1A1A - A→0A|1A| b. {w | w以相同的符号开始和结束} S→0A0|1A1 A→0A|1A| # 1, c. {w | w的长度为奇数} S→0A|1A A→0B|1B| B→0A|1A ! 0,1,0,01,10,- 0,1, d. {w | w的长度为奇数且正中间的符号为0} S→0S0|1S1|0S1|1S0|0 $ 0, 1,1,0 ,0, e. {w | w中1比0多} 1,0S→A1A 0,1（ A→0A1|1A0|1A|AA| R f. {w | w=w} S→0S0|1S1|1|0 、 ,$0,1,,1—, ,$ g. 空集 S→S ） 0,1,, 0,&0,01,1,,$ 给出产生下述语言的上下文无关文法： a． 字母表{a,b}上a的个数是b的个数的两倍的所有字符串组成的集合。 S→bSaSaS|aSbSaS|aSaSbS| nn b．语言{ab|n0}的补集。见问题中的CFG: S→aSb|bY|Ta T→aT|bT| *R c．{w#x | w, x{0,1}且w是x的子串}。 . S→UV U→0U0|1U1|W W→W1|W0|# V→0V|1V| d．{x1#x2##xk|kS→UVW U→A| A→aA|bA|#A|# [ V→aVa|bVb|#B|# B→aB|bB|#B|# W→B| 证明上下文无关语言类在并,连接和星号三种正则运算下封闭。 a. AB 方法一：CFG。设有CFG G1＝(Q1,,R1,S1)和G2=(Q2,,R2,S2)且L(G1)=A, L(G2)=B。构造CFG G=(Q,,R,S0)，其中 Q= Q1Q2{S0}, S0是起始变元，R= R1R2{S0 S1|S2}. ） 方法二：PDA。 设P1=(Q1,,1,1,q1,F1)识别A，P2=(Q1,,2,2,q2,F2)是识别B。 则如下构造的P=(Q,,,,q0,F)识别AB，其中 1) Q=Q1Q2{q0}是状态集， 2) ＝12，是栈字母表， 3) q0是起始状态， 4) F＝F1F2是接受状态集， 5) 是转移函数，满足对任意qQ, a,b ~ 1, 每一个xi{a,b} , 且存在i和j使得xi＝xj}。 *R {(q1,),(q2,)},若qq0,ab,(q,a,b),若qQ,b(),111(q,a,b)= (q,a,b),若qQ,b(),222,else.b. 连接AB 方法一：CFG。设有CFG G1＝(Q1,,R1,S1)和G2=(Q2,,R2,S2)且L(G1)=A, L(G2)=B。构造CFG G=(Q,,R,S0)，其中 Q= Q1Q2{S0}, S0是起始变元，R= R1R2{S0 S1S2}. 方法二：PDA。 设P1=(Q1,,1,1,q1,F1)识别A，P2=(Q1,,2,2,q2,F2)是识别B，而且P1满足在接受之前排空栈(即若进入接受状态，则栈中为空)这个要求。 则如下构造的P=(Q,,,,q1,F)识别AB，其中 1) Q=Q1Q2是状态集， 2) | ＝12，是栈字母表， 4) q1是起始状态， 5) F＝F1F2是接受状态集， 6) 是转移函数，满足对任意qQ, a 3) ,b 1(q,a,b),若qQ1F1,b(1),(q,a,b){(q,)},若qF1,ab,12(q,a,b)=1(q,a,b),若qF1,(a,b)(,), 2(q,a,b),若qQ2,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{S0S0S0|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) 是转移函数，满足对任意qQ, a,b : 1(q,a,b),若qQ1F1,(q,a,b){(q,)},若qF1,ab,11(q,a,b)=1(q,a,b),若qF1,(a,b)(,), (q1,)若qq0,ab,,else. 证明在节开始部分给出的文法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 含义是： 女孩用花碰这个男孩 ijk 给出产生语言A={abc| i,j,k0且或者i=j或者j=k}的上下文无关文法。你给出的文法是歧义的吗为什么 解：下面是产生A的一个CFG: SUV|AB UaUb| V 《 cV| AaA| BbUc| 这个CFG是歧义的，因为字符串abc有如下两种不同的最左派生： SUVaUbVabVabcVabc SABaAVaVabVcabc 给出识别中语言A的下推自动机的非形式描述。 解：其非形式描述为： | 此PDA有两个非确定性的分支：一个分支先读a，并且每读一个a将一个a推入栈中，当碰到b时，每读一个b从栈中弹出一个a，若没有a可弹出则拒绝，最后读c且不改变栈中的内容，若此时栈为空则接受。另一个分支也是先读a，但不改变栈中内容，当碰到b时，每读一个b将一个b推入栈中，再读c, 每读一个c从栈中弹出一个b，若没有a可弹出则拒绝，若c读完后栈为空则接受。开始时，读输入串的字符，非确定性的选择一个分支运行，若有一个分支接受则接受，否则拒绝。 设有上下文无关文法G: STT|U U0U00|# T0T|T0|# a. 用普通的语言描述L(G)。 b. 证明L(G)不是正则的。 ， 解： a. A={0#0#0| i, j, k0}{0#0| i p 2p i j k i 2i 0}。 p, |y|>0), xyz=0#0 n p+i 2p b. 取s=0#0, 则对于任意划分s=xyz(|xy|A, 所以不是正则 的。 用定理中给出的过程，把下述CFG转换成等价的乔姆斯基范式文法。 ABAB|B| B00| } 解：添加新起始变元S0, S0A ABAB|B| B00| 去掉A, S0A ABAB|AB|BA|B|BB … B 去掉B S0A ABAB|AB|BA|B| B00 A 去掉AB S0A BAB|AB|BA|00|BB B 00 00 去掉S0A, S0BAB|AB|BA|00|BB ABAB|AB|BA|00|BB B00 添加新变元 S0VB|AB|BA|UU|BB AVB|AB|BA|UU|BB BUU VBA U0 > 先说明如何把正则表达式直接转换成等价得上下文无关文法，然后利用问题xxx的结果，给出每一个正则语言都是上下文无关文法的一个证明。 解：设有正则表达式T，将其转化为上下文无关文法。 1) 首先添加ST，且令S为起始变元。 2) 根据T的不同形式，按如下方式添加规则 ①． 若T＝a， 则在规则集中添加Ta, ②． 若T＝， 则在规则集中添加T, ③． 若T＝， 则在规则集中添加TT， ④． 】 ⑤． 若T＝AB， 则在规则集中添加TA|B， ⑥． 若T＝A·B, 则在规则集中添加TAB， * ⑦． 若T＝A, 则在规则集中添加TA,和AAA| 3) 若有新添加的变元，则根据其所对应的表达式转第2步，直到没有新的变元出现。 下面来证明每一个正则语言都是上下文无关的 由正则语言与正则表达式的等价性可知：对于一个正则语言都存在一个描述他的正则表达式，由前述讨论可知，这个正则表达式可转换为一个与之等价的上下文无关的文法。因此，此正则语言能由这个上下文无关文法产生。所以正则语言是上下文无关的。 ] 2.18 a. 设C是上下文无关语言，R是正则语言。证明语言CR是上下文无关的。 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。下面构造识别CR的PDA如下S=(Q,,,,q0,F): 1) Q=Q1×Q2, 是状态集， 2) q0=(q1,q2)是起始状态， 3) F= F1×F2, 是接受状态集， 4) 是转移函数，满足对任意qQ1,rQ2,a,b, < ((q,r),a,b)={((q’,r’),c) | q’1(q,a), (r’,c)2(r,a,b)}. ***nnnnnn b. Aabc={abc|n0}, 若A是上下文无关的，则由a中命题知{abc|n0}也是上下文无关的，矛盾。 证明：设G是一个Chomsky范式CFG，则对任一长度2的字符串wL(G), w的任何派生恰好有2n－1步。 证明：(用数学归纳法)当n=2时，对于Chomsky范式CFG，长度为2的字符串必由3步派生，此时命题为真。 假设当2nk时命题为真。当n=k+1时，对于长度为k+1的字符串s=s1s2sk+1，存在S0的一个直接派生S0AB，使得A产生子串s1s2sp，B产生子串sp+1sp+2sk+1，其中1pk+1。由归纳假设，A产生子串s1s2sp需要2p-1步派生，而B产生子串sp+1sp+2sk+1需要2(k+1-p)-1步派生。因此，S0产生字符串s共需2(k+1)-1步派生。即当n=k+1时命题亦真。 因此，由G产生长度为n2的字符串需要2n-1派生。 : 用泵引理证明下述语言不是上下文无关的： nnnn a. {0101| n0} pppp 假设语言上下文无关，设p为泵长度，取S=0101.由泵引理知，S可以划分为uvxyz且满足泵引理条件。 22 考察子串vxy,首先，它一定横跨S的中点，否则，若vxy位于S的前半段，由于|vxy|p, 则uvxyz中 nnnn 1将是后半段字符串的第一个字符，即不可能是0101的形式。同理，vxy也不可能位于S后半段的位置 pijp 上。但是,若vxy跨越S的中点时，将S抽取成uxz，它形如0101,i，j不可能都为p，即uxz不可能是nnnn 0101的形式。 综上，可知S不能被抽取，因此，该语言不是上下文无关的。 n2n3n b. {0#0#0| n0} 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中#左侧的字符串长度也会大于右边。 ij 现在假设#x，则必存在不全为0的i,j，使得vy=10，下面分两种情况考虑： pp-ip-jp ①． j0, 则uxz=01#01不在该语言中 ②． $ 22 ③． j=0, 则uvxyz中#左侧的字符串长度大于右边，不在该语言中。 因此，该语言不是上下文无关的。 * d. {x1#x2##xk | k2, 每一个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不在该语言中。 综上该语言不是上下文无关的。 ] 考虑语言B=L(G), 其中G是练习中给出的文法。定理关于上下文无关语的泵引理称存在关于B的泵长度p。p的最小值等于多少要求给出证明。 ijk i2i 证明：p的最小值为4。令D={0#0#0| i, j, k0}, E={0#0| i0}, 则L(G)=DE。 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。 b 设G是一个含有b个变元的乔姆斯基范式CFG。证明：如果G产生某个字符串使用了至少2步的派生，则L(G)是无穷的。 T b R 证明：设G产生字符串S需要至少2步。 ？ 由于一个分支点(变元)对应一次派生，所以S的语法树τ至少有2个分支点。 R 又由于在乔姆斯基范式下，一个分支点至多有两个子分支点(这意味着层数 b n的结点个数2－1)，从而τ的由分支点组成的子树的高度大于等于b+1。 \" x y z u τ有一条路径上分支点(变元)个数b+1。由鸽巢原理：必有某个变元R在该路径上出现至少两次。不妨假设R出现在路径上最下面的b+1个变元中。 按上图所示，将S划分为uvxyz，在每一个R的下面有一棵子树，它产生S的一部分。上面的R有一棵较大的子树，产生vxy，下面的R有一棵较大的子树，产生x，由于这两棵子树由同一个变元产生，因而可 n 以相互替换。这里采用如下操作：反复用较大子树去替换较小子树，则我们得到对于任意n>1, uv xy n zL(G)。 所以若我们能证明v,y不全为ε，则L(G)是无穷的。 事实上，由乔姆斯基范式的特点，上面一个R的派生选择的必为RAB形式的规则，而且不可能有A和Bb ，所以v,y不全为。从而命题得证。 给出一个语言，它不是上下文无关的、但满足泵引理的三个条件。要求给出证明。 ijkl 解：令A＝{abcd| i,j,k,l0, 且当i=1时，j=k=l}，则： ijkl (1) A满足泵引理的三个条件。取泵长度p＝1。对A中任意长度大于1的字符串s= abcd，分情况可以如下抽取： ( 若i=1,则j=k=l, 取v=a,uxy=，z= bcd, 则对n0，uvxyz= abcd A； ij-1kl 若i2，且j,k,l不同时为0，不妨设j0，取u=a,v=b,xy=，z= bcd, 则对n0， jjj n n ijjj uvxyz= abcd A； i-1nni-1+n 若i2，且j=k=l=0, 取u=a,v=a,xyz=, 则对n0，uvxyz= aA； j-1kl 若i=0，则j,k,l不同时为0，不妨设j0，取v=b,uxy=，z= bcd, 则对n0，nnj-1+nkl uvxyz=bcd A。 *** (2) A不是上下文无关语言。事实上，若A为上下文无关语言，另取正则语言R=abcd，由问题 nnn 可知，LR是上下文无关的。但这与LR={abcd| n0}不是一个上下文无关语言矛盾。因此，A不是上下文无关的。 修改定理以得到推论的证明，即证明一个语言是可判定的当且仅当有非确定的TM判定它。 证明：若M是一个确定型判定器则，则M也是一个非确定型判定器。 } 现在设N是一个非确定的判定器，将构造一个与之等价的确定型判定器M。模拟过程使用深度搜索。 设N的不确定性分支的最大个数为b。 M有三个带：一个输入带，一个工作带，一个地址带。M按深度优先方式搜索N的不确定计算分支树。 M= “输入w， 1) 初始化，第一带上为w, 第二带为空，第三带为1; 2) 将第一带的内容复制到第二带上， 3) 按当前地址位数字选择N的一个不确定性分支，在第二带上模拟N运行一步； 4) 若当前地址位为i 5) （ nnij-1+nkl 6) 若当前地址位为i＝b，且当前选择无效或按当前选择进入拒绝状态，则将当前地址位改为空 格, 左移并将当前地址位改为空格直到找到一个地址位其值 由于N是非确定型判定器，所以对任意输入，由本题的提示M一定会停机。 给出枚举器的形式定义。 解：枚举器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表示一个空格。 检查图灵机的形式定义，回答下列问题并解释你的推测： a． 图灵机能在它的带子上写下空白符吗 b．带字母表和输入字母表能相同吗 c．图灵机的读写头能在连续的两步中处于同一个位置吗 d．图灵机能只包含一个状态吗 。 解： a．能。因为空白符属于带字母表； b．不能。因为空白符不属于输入字母表； c．能。当读写头处于左端点时，如果转移是向左转移，因为不准机器从带的左端点移出，所以下一个格 局读写头仍在左端点。 d．不能。因为qacceptqreject，至少应有两个状态。 解：因为M不一定是判定器，可能会在运行某个si时不停机，则L(M)中按字典序大于si的字符串不可能被枚举出来。 … 解：因为图灵机的一个本质要求是一步之内，只能做有限的工作，而第1)步中取所有可能的值，这有无限多种情况。 构造具有3条带的图灵机。 对于问题a. 1) w 先读入第一条带，然后读到0就把0写入第2条带，读到1就把1写入第3条带，直到读到空 格为止。 2) 然后把3个读写头都返回到最左边。 3) 开始读第2条带和第3条带，每次都是读一个字符，如果同时遇上空格符，则接收，否则拒绝。 ` 对于问题b: 1) 和a的第1步相同。 2) 和a的第2步相同。 3) 每次读带3的一个字符就读带2的两个字符，如果同时遇上空格符，就接收，否则拒绝。 对于问题c: 1) 和a的第1步相同。 2) 和a的第2步相同。 3) 每次读带3的一个字符就读带2的两个字符，如果同时遇上空格符，就拒绝，否则接受。 { 由题知,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． | c． 栈A,B,C中若有弹出，则在相应带上当前格改写为空格，并左移一格；若有推入a，则 在相应带上右移一格，并写入a。 3) 若P进入接受状态，则接受。” 证明双无限带图灵机识别图灵可识别语言。 证明思路：利用双无限单带图灵机模拟普通单带图灵机时，只需要设计一个左端点。我们的证明是让它在第一格左边标记“$”作为左端点。 证明： 首先用单带双无限带图灵机模拟普通单带图灵机： 设有普通图灵机M1＝( Q1, , 1, 1, q0, qaccept, qreject )。 下面构造与之等价的单带双无限带图灵机M2＝( Q2, , 2, 2, qs, qaccept, qreject )，其中 ； Q2=Q1{qs,qt}, qs为新的起始状态；对任意qQ2, a2, 2 ＝ 1 {$}. 若 qqs,(qt,a,L),(q,$,R),若 qq,t2(q,a)0 (q,a),若 qQ1 , a1,1若 qQ1 , a$.(q, $, R)，再用普通单带图灵机模拟单带双无限带图灵机： 设有单带双无限图灵机M1＝(Q,,,,q0,qaccept,qreject)，下面构造普通单带图灵机M2： M2=“输入串w， 1) 将带上字符串改写为$w, 将读写头放在w的第一个字符上， 2) 按照M1的转移函数运行， 3) 》 4) 每当读写头移到了$上，就将$右边的所有字符右移一格，并在$右边的方格里写上空格符，再 将读写头放在这个方格上，转第二步， 5) 若进入接受状态，则接受；若进入拒绝状态则拒绝。” 也可以用普通双带图灵机模拟单带双无限带图灵机： 设有单带双无限图灵机M1＝(Q,,,,q0,qaccept,qreject)，下面构造普通双带图灵机M2： M2=“输入串w， 1) 在第一个带上放上$, 读写头放在$上； 第二个带子上放入#w, 读写头放在第二个方格上。 2) \\ 3) 当第一带读写头位于$上，而第二带读写头不在＃上时，在第二带上按照M1的转移规则运行， 直到停机或读写头移到#上。若进入接受状态则接受，若进入拒绝状态则拒绝。若读写头移到#上，则将第一带上读写头右移一格。 4) 当第二带读写头位于#上，而第一带读写头不在$上时，在第一带上按照M1的转移规则运行， 但是每一步要将读写头移动方向反向，直到停机或读写头移到$上。若进入接受状态则接受，若进入拒绝状态则拒绝。若读写头移到$上，则将第二带上读写头右移一格，转第二步。” 只写一次图灵机是一个单带图灵机，它在每个带方格上最多只能改变其内容一次(包括带上得输入区域)。证明图灵机模型的这个变形等价于普通的图灵机模型。 证明：普通单带图灵机总是可以模拟只写一次图灵机。下面说明怎样用一个只写一次TM T 模拟一个普通单带TM S。 T=“对于输入w=w1w2wn, 1) 在w1w2wn上并模拟S运行。 2) 每当S要改写工作带时(例如设S要将当前方格内容改写为b，并且左移或右移一格)，T按如下 方式动作： … a. 将当前方格改写为“b*”，在带子右边第一个空格写下“#”。 b. 将“#”左边的字符抄写到“#”右边(注：每抄写一个字符，需要将此格字符改写一次以作上标记，但是“b*”不用再作另外标记，而且将“b*”抄写为“b~”)。 c. 找到带有标记“~”的字符，再模拟S左移或右移一格。 然后继续模拟S。 3) 若S接受则接受；若S拒绝则拒绝。” 对于普通图灵机N，构造与之等价的带左复位的图灵机E： & E＝“对于输入w, 1) 在w上模拟N的一步动作： 2) 若N要将当前格由a改为b且右移，则照此动作； # 3) 若N要将当前格由a改为b且左移，则将当前格由a改为b且复位： a) 以~标记当前位，右移一格； b) 若当前位没有标记#，则复位，右移直到找到标记有~的字符，去掉此标记，右移一格转步(a); c) 若当前位有标记#，则去掉标记#并复位，右移或直到找到标记有~的字符，去掉此标记； 4) 若N进入接受状态，则接受；若进入拒绝状态，则拒绝；否则转第一步。” L(E)=L(N)。因此左复位的图灵机识别图灵可识别语言类。 、 以停留代替左移的图灵机识别什么语言类 解：正则语言类。首先一个DFA可以被一个以停留代替左移的图灵机模拟。下面证明一个以停留代替左移的图灵机S=(Q,,,,q1,qaccept,qreject)，可以被一个NFA M=(Q1,,1,q0,F)模拟。 M的构造如下： 令Q1= Q×{qend}， F={qend}，q0=(q1,), 1) 对任意qQ-{qaccept,qreject}, a,令 ) , a )={(q,a)}; 1( (q, 2) 对任意qQ-{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) 对任意qQ，令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最终会进入拒绝状态或不停机。 证明可判定语言类在下列运算下封闭。 a. 并。 证明：设M1，M2为识别可判定语言A1,A2的判定器。构造图灵机M： M＝“输入w， 1) 分别在w上运行M1和M2，每运行一步M1就运行一步M2。 2) 若M1和M2中有一个接受，则接受。 { 若都拒绝，则拒绝。” M为识别A1A2的判定器。所以可判定语言类对并运算封闭。 b. 连接。 证明：设M1，M2为识别可判定语言A1,A2的判定器。构造图灵机M： M＝“输入w， 1) 列出所有将w分成两段的方式(|w|+1种). 2) 对于每一种分段方式，在第一段上运行M1，在第二段上运行M2。若都接受，则接受。 3) 若没有一种分段方式被接受则拒绝。” 、 M为识别A1A2的判定器。所以可判定语言类对连接运算封闭。 c. 星号。 证明：设M1为识别可判定语言A的判定器。 M＝“输入w， |w|-1 1) 列出w的所有分段的方式(2种)。 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为识别A1A2的判定器。所以可判定语言类对交运算是封闭的。 证明图灵可识别语言类在下列运算下封闭： 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识别A1A2。所以图灵可识别语言类对并运算是封闭的。 b. M＝“输入w， 1) 出所有将w分成两段的方式(|w|+1种). 2) 对于i=1,2,重复以下步骤： 3) 对于每一种分段方式，在第一段上运行M1i步，在第二段上运行M2 i步，或者直到停机。若 都接受，则接受。” M识别A1A2。所以图灵可识别语言类对连接运算是封闭的。 c．M＝“输入w， 1) [ |w|-1 2) 列出w的所有分段的方式(2种). 3) 对于i=1,2,重复以下步骤： 4) 对于每一种分段方式，分别在每一段上运行M1 i步，或者直到停机。 若M1接受所有段，则接受。” * M识别A。所以图灵可识别语言类对星号运算是封闭的。 d．M= “对于输入w： 考虑DFA和正则表达式是否等价的问题。将这个问题表示为一个语言并证明它可判定。 解：设EQD-R={ F=“对于输入 1) 将正则表达式B转化为等价的DFA C。 2) 检测A与C是否等价(EQDFA可判定)。 3) 若等价，则接受；否则拒绝。” F判定EQD-R。 * 设ALLDFA={ | A是一个识别的DFA}。证明ALLDFA可判定。 证明： @ 方法一：设计一个使用标记算法的TM M, M=“对于输入,其中A是一个DFA: 1) 去掉除起始状态以外的所有无用状态。标记起始状态。 2) 重复下列步骤，直到没有新的状态可被标记。 3) 对于每一个未标记状态，如果有一个到达它的转移是从某个已被标记过的状态出发的， 则将其标记。 4) 如果所有的标记状态都是接受状态，则接受；否则拒绝” * 方法二：构造DFA B，使得L(B)= 。 M＝“对于输入,其中A是一个DFA: 1) * 2) 检测 3) 若等价，则接受；若不等价，则拒绝。” 4.4 ACFG={ 1) 构造与G等价的Chomsky文法P。 2) 若P的规则集中有S0(其中S0为起始变元)，则接受；否则拒绝。” M判定ACFG。 | 设INFTYDFA={|A是一个DFA，且L(A)是一个无限语言}。证明INFTYDFA是可判定的。 证明：要证一个DFA识别一个无限语言，只需证此DFA的状态图中有回路。 M=“对于输入，其中A是一个DFA： 1) 若无接受状态则拒绝。 2) 去掉A中所有无用状态(没有从它出发到达任何接受状态的路径)。 3) 若起始状态被去掉，则拒绝。 4) 重复下一步，直到没有新的状态被标记。 5) 考察每一个未标记的状态，如果没有到它的转移(射入的箭头)，则将其标记并去掉所有 从它出发的转移(射出的箭头)。 6) 若所有状态都被标记，则拒绝；否则接受。” `