设
L
L
L是一个
R
L
RL
RL，
D
F
A
?
M
=
(
Q
,
Σ
,
δ
,
q
0
,
F
)
DFA \ M = (Q , \Sigma , \delta , q_{0} , F)
DFA?M=(Q,Σ,δ,q0?,F)，满足
L
(
M
)
=
L
L(M) = L
L(M)=L，
∣
Q
∣
=
N
|Q| = N
∣Q∣=N，不失一般性，不妨假设
Q
Q
Q中不含任何不可达状态
取
L
L
L的句子
z
=
a
1
a
2
?
a
m
(
m
≥
N
)
z = a_{1} a_{2} \cdots a_{m} (m \geq N)
z=a1?a2??am?(m≥N)，对
?
h
\forall h
?h，
1
≤
h
≤
m
1 \leq h \leq m
1≤h≤m，令
δ
(
q
0
,
a
1
a
2
?
a
h
)
=
q
h
\delta(q_{0} , a_{1} a_{2} \cdots a_{h}) = q_{h}
δ(q0?,a1?a2??ah?)=qh?
由于
m
≥
N
m \geq N
m≥N，所以在状态序列
q
0
,
q
1
,
?
?
,
q
N
q_{0} , q_{1} , \cdots , q_{N}
q0?,q1?,?,qN?中至少有两个状态是相同的，不妨假设
q
k
q_{k}
qk?与
q
j
q_{j}
qj?是该状态序列中最早出现的相同状态，显然
k
<
j
≤
N
k < j \leq N
k<j≤N
此时有
δ
(
q
0
,
a
1
a
2
?
a
k
)
=
q
k
δ
(
q
k
,
a
k
+
1
?
a
j
)
=
q
j
=
q
k
δ
(
q
j
,
a
j
+
1
?
a
m
)
=
q
m
\begin{aligned} \delta(q_{0} , a_{1} a_{2} \cdots a_{k}) &= q_{k} \\ \delta(q_{k} , a_{k + 1} \cdots a_{j}) &= q_{j} = q_{k} \\ \delta(q_{j} , a_{j + 1} \cdots a_{m}) &= q_{m} \end{aligned}
δ(q0?,a1?a2??ak?)δ(qk?,ak+1??aj?)δ(qj?,aj+1??am?)?=qk?=qj?=qk?=qm??
注意到
q
j
=
q
k
q_{j} = q_{k}
qj?=qk?，所以对于任意整数
i
≥
0
i \geq 0
i≥0
δ
(
q
k
,
(
a
k
+
1
?
a
j
)
i
)
=
δ
(
q
k
,
(
a
k
+
1
?
a
j
)
i
?
1
)
?
=
δ
(
q
k
,
a
k
+
1
?
a
j
)
=
q
k
\begin{aligned} \delta(q_{k} , (a_{k+1} \cdots a_{j})^{i}) &= \delta(q_{k} , (a_{k+1} \cdots a_{j})^{i - 1}) \\& \cdots \\ &= \delta(q_{k} , a_{k+1} \cdots a_{j}) \\ &= q_{k} \end{aligned}
δ(qk?,(ak+1??aj?)i)?=δ(qk?,(ak+1??aj?)i?1)?=δ(qk?,ak+1??aj?)=qk??
因为
z
∈
L
(
M
)
z \in L(M)
z∈L(M)，所以
q
m
∈
F
q_{m} \in F
qm?∈F，故对于任意整数
i
≥
0
i \geq 0
i≥0，
δ
(
q
0
,
a
1
a
2
?
a
k
(
a
k
+
1
?
a
j
)
i
a
j
+
1
?
a
m
)
=
q
m
\delta(q_{0} , a_{1} a_{2} \cdots a_{k} (a_{k + 1} \cdots a_{j})^{i} a_{j + 1} \cdots a_{m}) = q_{m}
δ(q0?,a1?a2??ak?(ak+1??aj?)iaj+1??am?)=qm?，也就是说
a
1
a
2
?
a
k
(
a
k
+
1
?
a
j
)
i
a
j
+
1
?
a
m
∈
L
(
M
)
a_{1} a_{2} \cdots a_{k} (a_{k + 1} \cdots a_{j})^{i} a_{j + 1} \cdots a_{m} \in L(M)
a1?a2??ak?(ak+1??aj?)iaj+1??am?∈L(M)
取
u
=
a
1
a
2
?
a
k
v
=
a
k
+
1
?
a
j
w
=
a
j
+
1
?
a
m
\begin{aligned} u &= a_{1} a_{2} \cdots a_{k} \\ v &= a_{k + 1} \cdots a_{j} \\ w &= a_{j + 1} \cdots a_{m} \end{aligned}
uvw?=a1?a2??ak?=ak+1??aj?=aj+1??am??
对于任意整数
i
≥
0
i \geq 0
i≥0，
u
v
i
w
∈
L
u v^{i} w \in L
uviw∈L，注意到
k
<
j
≤
N
k < j \leq N
k<j≤N，所以
u
u
u，
v
v
v满足
∣
u
v
∣
≤
N
∣
v
∣
≥
1
|uv| \leq N \\ |v| \geq 1
∣uv∣≤N∣v∣≥1
正则语言的泵引理
设
L
L
L为一个
R
L
RL
RL，则存在仅依赖于
L
L
L的正整数
N
N
N，对于
?
z
∈
L
\forall z \in L
?z∈L，如果
∣
z
∣
≥
N
|z| \geq N
∣z∣≥N，则存在
u
u
u，
v
v
v，
w
w
w满足：
z
=
u
v
w
z = uvw
z=uvw
∣
u
v
∣
≤
N
|uv| \leq N
∣uv∣≤N
∣
v
∣
≥
1
|v| \geq 1
∣v∣≥1
对于任意整数
i
≥
0
i \geq 0
i≥0，
u
v
i
w
∈
L
u v^{i} w \in L
uviw∈L
N
N
N不大于接受
L
L
L的最小
D
F
A
?
M
DFA \ M
DFA?M的状态数
泵引理给出的是
R
L
RL
RL的“必要条件”而不是“充分条件”
应用
问题
1
1
1
证明
{
?
0
n
1
n
∣
n
≥
1
?
}
\set{0^{n} 1^{n} \mid n \geq 1}
{0n1n∣n≥1}不是
R
L
RL
RL
解答
1
1
1
设
L
=
{
?
0
n
1
n
∣
n
≥
1
?
}
L = \set{0^{n} 1^{n} \mid n \geq 1}
L={0n1n∣n≥1}，假设
L
L
L是
R
L
RL
RL，则它满足泵引理，不妨设
N
N
N是泵引理所指的仅依赖于
L
L
L的正整数
取
z
=
0
N
1
N
z = 0^{N} 1^{N}
z=0N1N，显然
z
∈
L
z \in L
z∈L，按照泵引理所述，必存在
u
u
u，
v
v
v，
w
w
w，由于
∣
u
v
∣
≤
N
|uv| \leq N
∣uv∣≤N，并且
∣
v
∣
≥
1
|v| \geq 1
∣v∣≥1，所以
v
v
v只可能是由
0
0
0组成的非空串
不妨设
v
=
0
k
,
k
≥
1
v = 0^{k} , k \geq 1
v=0k,k≥1
此时有
u
=
0
N
?
k
?
j
w
=
0
j
1
N
\begin{aligned} u &= 0^{N - k - j} \\ w &= 0^{j} 1^{N} \end{aligned}
uw?=0N?k?j=0j1N?
从而有
u
v
i
w
=
0
N
?
k
?
j
(
0
k
)
i
0
j
1
N
=
0
N
+
(
i
?
1
)
k
1
N
u v^{i} w = 0^{N - k - j} (0^{k})^{i} 0^{j} 1^{N} = 0^{N + (i - 1) k} 1^{N}
uviw=0N?k?j(0k)i0j1N=0N+(i?1)k1N
当
i
=
2
i = 2
i=2时，有
u
v
2
w
=
0
N
+
(
2
?
1
)
k
1
N
=
0
N
+
k
1
N
?
L
u v^{2} w = 0^{N + (2 - 1) k} 1^{N} = 0^{N + k} 1^{N} \notin L
uv2w=0N+(2?1)k1N=0N+k1N∈/L，与泵引理矛盾，所以
L
L
L不是
R
L
RL
RL
问题
2
2
2
证明
{
?
0
n
∣
n
为素数
?
}
\set{0^{n} \mid n 为素数}
{0n∣n为素数}不是
R
L
RL
RL
解答
2
2
2
设
L
=
{
?
0
n
∣
n
为素数
?
}
L = \set{0^{n} \mid n 为素数}
L={0n∣n为素数}，假设
L
L
L是
R
L
RL
RL，则它满足泵引理，不妨设
N
N
N是泵引理所指的仅依赖于
L
L
L的正整数
取
z
=
0
N
+
p
z = 0^{N + p}
z=0N+p，其中
N
+
p
N + p
N+p是素数，即
z
∈
L
z \in L
z∈L，按照泵引理所述，必存在
u
u
u，
v
v
v，
w
w
w，由于
∣
v
∣
≥
1
|v| \geq 1
∣v∣≥1，所以
v
v
v必定是由
0
0
0组成的非空串
不妨设
v
=
0
k
,
k
≥
1
v = 0^{k} , k \geq 1
v=0k,k≥1
此时有
u
=
0
N
+
p
?
k
?
j
w
=
0
j
\begin{aligned} u &= 0^{N + p - k - j} \\ w &= 0^{j} \end{aligned}
uw?=0N+p?k?j=0j?
从而有
u
v
i
w
=
0
N
+
P
?
k
?
j
(
0
k
)
i
0
j
=
0
N
+
p
+
(
i
?
1
)
k
u v^{i} w = 0^{N + P - k - j} (0^{k})^{i} 0^{j} = 0^{N + p + (i - 1) k}
uviw=0N+P?k?j(0k)i0j=0N+p+(i?1)k
当
i
=
N
+
p
+
1
i = N + p + 1
i=N+p+1时，
u
v
N
+
p
+
1
w
=
0
(
N
+
p
)
(
1
+
k
)
?
L
u v^{N + p + 1} w = 0^{(N + p)(1 + k)} \notin L
uvN+p+1w=0(N+p)(1+k)∈/L，与泵引理矛盾，所以
L
L
L不是
R
L
RL
RL