§4.6 上下文无关语言的性质
1. 2 型语言的泵浦引理:
设 L 是上下文无关语言,存在常数 p,如果ω∈ L,
且︱ω︱≥ p,则ω可以写为ω=ω
1
ω
2
ω
0
ω
3
ω
4
,使ω
2
ω
3
≠
ε,∣ω
2
ω
0
ω
3
∣≤ p,对于 i ≥0 有ω
1
ω
i
2
ω
0
ω
i
3
ω
4
∈L。(不
含 L={ ε} 的情况)
物理意义:
线性语言的泵浦引理是说, 在正规集合中, 每个足够长的字
符串都包含一个短的字串, 随便将这个子串在原处重复插入多少
次,所得的新字串还是在原正规集中。
2 型语言的泵浦引理是说,有两个靠得很近的子串,它们可
以重复任意多次(但二者重复的次数相同) ,所得的新串依然属
于该 2 型语言。
证明:
设 G是 Chomsky文法(形如 A→BC,A→a), 产生语言 L-{ ε}
若ω∈ L 且ω有一定的长度, 则边缘为ω的推导树有一定长
度的路径。
对于 Chomsky范式,设路径长度为 n,则有边缘长度
︱ω︱≤ 2
n-1
,如下图所示
S
a
路径 =1
︱ω︱=︱ a︱= 2
1- 1
=1
S
A B
a a
路径 = 2
︱ω︱=︱ aa︱= 2
2 - 1
=2