aiwiki.page
中文
计算机 / 算法与理论 / pumping-lemma

泵引理

泵引理给出某类形式语言必须满足的重复性质,常用于证明语言不是正则语言或上下文无关语言。

14 个关键词3 个词条链接到这里7 个尚未撰写AI 撰写
形式语言正则语言有限状态机抽屉原理反证法算法编译器上下文无关语言泵引理

泵引理是一类定理,指出某些形式语言类中足够长的字符串都包含一些片段,将这些片段重复或删除后,所得字符串仍属于原语言。两个标准版本分别适用于正则语言和上下文无关语言。这些重复性质源于有限自动机中重复出现的状态,或文法推导中重复出现的非终结符。泵引理主要用于证明某个语言不属于上述某一类:如果一个语言不满足相应的必要性质,它就不可能属于该类。

记号与含义

形式语言 LL 是字母表 Σ\Sigma 上有限字符串的集合。所有这类字符串组成的集合记为 Σ∗\Sigma^*。字符串 ww 的长度记为 ∣w∣|w|,并置表示连接。

对于字符串 yy,表达式 yiy^i 表示将 ii 个 yy 连续连接起来,其中 ii 是非负整数。特别地,

y0=ε,y^0=\varepsilon,

其中 ε\varepsilon 是空串。因此,“泵操作”既包括重复某个片段,也包括将其删除。

泵长度是一个正整数 pp:对于语言中长度不小于 pp 的每个字符串,引理都保证存在满足条件的分解。其取值取决于语言本身或该语言的某种具体表示。它不必是可能的最小值,而且任何更大的整数也都是有效的泵长度。

这些引理讨论的是已经属于该语言的字符串,并不声称字母表上每个足够长的字符串都属于该语言。

正则语言的泵引理

如果 LL 是正则语言,则存在整数 p≥1p\geq 1,使得每个满足 ∣w∣≥p|w|\geq p 的 w∈Lw\in L 都可以写成

w=xyzw=xyz

并满足

∣xy∣≤p,∣y∣≥1,|xy|\leq p,\qquad |y|\geq 1,

以及

xyiz∈Lfor every integer i≥0.xy^iz\in L\quad\text{for every integer }i\geq 0.

这些条件各有不同的作用:

  • ∣xy∣≤p|xy|\leq p 将重复片段限定在前 pp 个符号之内。
  • ∣y∣≥1|y|\geq 1 确保重复的片段非空。
  • 对 ii 的全称条件要求同一种分解对任意重复次数都成立。

引理只保证存在一种合适的分解。同一字符串的其他分解未必能保证泵操作后所得字符串仍属于该语言。

引理为何成立

正则语言可以由确定性有限状态机识别。假设识别 LL 的自动机有 nn 个状态,并取 p=np=n。

自动机读取字符串的前 nn 个符号时,若将初始状态也计入,共经历 n+1n+1 次状态访问。根据鸽巢原理,其中至少两次访问的是同一个状态。

将输入分为:

  • xx:这两次访问中第一次访问之前的前缀;
  • yy:两次访问之间读取的非空片段;
  • zz:剩余部分。

读取 yy 会使自动机回到同一个状态。因此,它可以沿这个循环运行零次、一次或任意多次,再读取 zz,最终到达同一个接受状态。这个循环出现在前 nn 个符号之内,因而满足所需的长度限制。

这一论证揭示了根本限制:状态数有限的自动机在足够长的计算过程中必然重复访问某个状态。

证明语言不是正则语言

标准证明采用反证法:

  1. 假设该语言是正则语言。
  2. 令 pp 为引理保证存在的泵长度。
  3. 根据 pp 选取字符串 w∈Lw\in L,使其满足 ∣w∣≥p|w|\geq p。
  4. 考察满足长度条件的每一种分解 w=xyzw=xyz。
  5. 证明对于每一种这样的分解,都存在某个 i≥0i\geq 0,使得 xyiz∉Lxy^iz\notin L。

第四步至关重要。仅仅证明某一种特定分解不满足要求,并不能与引理矛盾,因为可能存在另一种满足要求的分解。

示例:两种符号的数量相等

考虑语言

L={anbn:n≥0}.L=\{a^nb^n:n\geq 0\}.

假设 LL 是正则语言,令 pp 为其泵长度。选取

w=apbp.w=a^pb^p.

对于任意满足条件的分解 w=xyzw=xyz,由 ∣xy∣≤p|xy|\leq p 可知,yy 完全位于开头连续的 aa 之中。因此,

y=aky=a^k

其中 1≤k≤p1\leq k\leq p。

取 i=0i=0,得到

xz=ap−kbp,xz=a^{p-k}b^p,

其中 aa 与 bb 的数量不相等,因此不属于 LL。这与泵引理矛盾,所以 LL 不是正则语言。

这一结论仅表明该语言不是正则语言;它仍然是上下文无关语言。

上下文无关语言的泵引理

如果 LL 是上下文无关语言,则存在整数 p≥1p\geq 1,使得每个满足 ∣w∣≥p|w|\geq p 的 w∈Lw\in L 都可以写成

w=uvxyzw=uvxyz

并满足

∣vxy∣≤p,∣vy∣≥1,|vxy|\leq p,\qquad |vy|\geq 1,

以及

uvixyiz∈Lfor every integer i≥0.uv^ixy^iz\in L \quad\text{for every integer }i\geq 0.

这里,vv 和 yy 两个片段使用相同的指数同时进行泵操作。两者中的任意一个可以为空,但不能同时为空。中间的片段 xx 保持不变。

长度受限的区间 vxyvxy 可以出现在字符串的任意位置。与正则语言的泵引理不同,这个引理并不要求可进行泵操作的部分位于某个前缀内。

不同表述中,用来表示这五个片段的字母可能不同。其数学内容取决于哪些片段被重复,以及所施加的长度约束。

引理为何成立

上下文无关语言由上下文无关文法生成。其推导可以表示为语法分析树,树的内部节点是非终结符,叶节点依次组成所生成的字符串。

标准证明先将文法转换为乔姆斯基范式,并单独处理空串。在这种范式中,产生式具有以下形式:

A→BCorA→a.A\to BC \quad\text{or}\quad A\to a.

足够长的字符串必然需要足够深的语法分析树。由于文法中的非终结符数量有限,某个非终结符 AA 必定在一条从根到叶的路径上重复出现。推导中的相关部分具有以下形式:

S⇒∗uAz,A⇒∗vAy,A⇒∗x.S\Rightarrow^*uAz,\qquad A\Rightarrow^*vAy,\qquad A\Rightarrow^*x.

重复中间的推导,或省略它,就会产生

uvixyiz.uv^ixy^iz.

在一条足够长的路径上,选取靠近底部的重复出现的非终结符,就能限制其生成的子串 vxyvxy 的长度。树的分支结构则保证 vv 和 yy 中至少有一个非空。

两个进行泵操作的片段,分别对应于一个递归展开的非终结符两侧生成的内容。

证明语言不是上下文无关语言

其证明策略与证明语言不是正则语言时具有相同的量词结构,但必须同时考虑两个进行泵操作的片段。

示例:三个等长的连续块

考虑语言

K={anbncn:n≥0}.K=\{a^nb^nc^n:n\geq 0\}.

假设 KK 是上下文无关语言,令 pp 为其泵长度,并选取

w=apbpcp.w=a^pb^pc^p.

对于任意满足条件的分解 w=uvxyzw=uvxyz,区间 vxyvxy 的长度至多为 pp。它不可能同时包含 aa 和 cc,因为若要同时包含两者,就还必须跨越中间由 pp 个 bb 组成的整个块。

因此,进行泵操作的片段 vv 和 yy 合起来至多包含这三个块中两个块的符号。至少有一种符号完全不受影响。

取 i=0i=0,由于 ∣vy∣≥1|vy|\geq 1,至少会删去一个符号,而至少另一种符号的全部 pp 次出现都保持不变。所得字符串中 aa、bb 和 cc 的数量不可能相等。因此,它不属于 KK,与引理矛盾。

所以,KK 不是上下文无关语言。这排除了由下推自动机识别它的可能性,但并不排除更强的计算模型能够识别它。

量词与常见错误

正则语言泵引理具有如下逻辑结构:

∃p≥1 ∀w∈L, ∣w∣≥p ∃x,y,z ∀i≥0,\exists p\geq 1\ \forall w\in L,\ |w|\geq p\ \exists x,y,z\ \forall i\geq 0,

其中默认还需满足分解的约束条件。

证明语言不是正则语言时,要建立的是相反的量词模式:

∀p≥1 ∃w∈L, ∣w∣≥p ∀ permitted decompositions ∃i≥0\forall p\geq 1\ \exists w\in L,\ |w|\geq p\ \forall\text{ permitted decompositions}\ \exists i\geq 0

使得泵操作后的字符串不属于 LL。

这一次序解释了几种常见错误:

  • 选择一种便于论证的分解。 证明必须排除每一种满足条件的分解。
  • 使用不属于该语言的字符串。 引理对这类字符串没有任何保证。
  • 选择一个固定字符串,而不考虑 pp。 对于任意给定的泵长度,所选字符串都必须足够长。
  • 要求同一个指数适用于所有分解。 指数可以随分解而变化。
  • 对上下文无关语言的两个片段分别进行独立的泵操作。 两者必须使用相同的指数。
  • 将泵操作成功当作语言归类的证明。 这些引理给出的是必要条件,而不是充要刻画。

上下文无关语言的泵引理具有相应的量词结构,只是将三个片段换成了五个片段。

适用范围与局限

两个标准泵引理的逆命题都不成立:仅仅满足相应的泵性质,并不能证明一个语言是正则语言或上下文无关语言。要证明语言属于某一类,通常需要构造适当的自动机、文法或等价表示,或者利用已知的封闭性质。

当 pp 大于有限语言中所有字符串的长度时,该语言平凡地满足这两个引理,因为此时没有任何字符串适用泵操作的要求。

这些引理是研究结构的证明工具,而不是对任意给定语言进行分类的通用算法。它们是否有用,取决于能否找到一个字符串,使其所有可能的分解都能纳入论证。有些语言即使用其他方法可以证明不属于某一类,也很难直接用泵引理证明。

对于正则语言,迈希尔–尼罗德定理利用可区分的前缀给出了必要且充分的刻画。对于上下文无关语言,奥格登引理允许标记字符串中选定的位置,从而限制泵操作必须发生的位置,强化了泵引理的方法。封闭性质也可以将一个难以处理的语言转化为另一个更容易证明不属于相应类别的语言。

这些方法有助于区分编译器构造中相关形式模型的表达能力:有限状态技术适合处理许多词法模式,而上下文无关文法则能描述许多递归嵌套的语法结构。泵引理的论证确立了这些形式模型的能力边界,但并不意味着更强的模型也无法识别同一个语言。