1. 泵引理在证明什么把“有限状态”翻译成“必然重复”几乎所有讲计算理论的课程都会把泵引理Pumping Lemma放在正则语言那一章的后半段但它出现的时机很尴尬前面刚学完 DFA、NFA、正则表达式三者的等价性后面马上要进入上下文无关文法和下推自动机。很多人囫囵吞枣地背下三个条件考试能套着用但一到“为什么这三个条件就够用”就卡住。我自己第一次看的时候也是这样直到把它的证明拆成“有限个状态 一条足够长的路径”这两件事才真正把它当成一个可以随手复现的工具而不是需要死记的公式。先把结论摆出来。设 L 是一个正则语言那么存在一个常数 p通常叫泵长度pumping length使得 L 中任意长度不小于 p 的字符串 w都可以切成三段 w xyz并且同时满足三条|y| ≥ 1也就是被“泵”的那一段不能是空串|xy| ≤ p也就是被泵的那一段必须出现在足够靠前的位置对所有 i ≥ 0xyⁱz 都属于 L。注意第三条里的 i 是从 0 开始的非负整数包括 i 0也就是把 y 整个删掉。这一点在后续用它做反证时是主战场因为 i 0 往往是最容易构造出矛盾的取值。1.1 三个条件各自承担的角色这三条不是随手凑出来的每一条都在为后续的“反证”服务。|y| ≥ 1 保证了泵这个动作真的改变了字符串如果允许 y 是空串那 xyⁱz 永远等于原串条件就变成了一句废话任何语言都满足。|xy| ≤ p 保证了被泵的那一段落在字符串前面的有限窗口里这是证明过程中“鸽巢原理”能够生效的直接后果也是后面构造矛盾时我们唯一能确定位置的依据。第三条则是结论本身它把“可以无限次重复”这件事写成了对所有 i 成立的全称命题——正是这个全称量词给了我们挑选某个特定 i 来制造反例的自由。换个角度理解前两条是在描述“y 长什么样、在哪”第三条是在描述“y 能干什么”。做证明题时前两条限制你只能在前 p 个字符里找 y第三条给你无限的火力去挑 i。1.2 一个容易被忽略的前提语言必须是正则的泵引理的陈述里“L 是正则语言”是前提不是结论。这意味着它是一条必要条件只在“正则 ⇒ 可泵”这个方向成立。很多人做题时下意识地反着用看到某个语言可以泵就说它正则这是典型的逻辑倒错。正则有泵引理但可泵不等于正则后面第 4 章会专门讲这件事。另外p 是一个与具体字符串无关的常数只取决于语言本身——更准确地说取决于接受这个语言的 DFA 的状态数。它不需要你算出来具体是多少在反证过程中我们只用到“p 存在”这一事实然后可以假设 p 任意大构造一个比 p 更长的字符串来触发矛盾。1.3 反向读它其实是一个“非存在性”工具正着读泵引理说的是一件所有正则语言都具备的性质是一句“有”的断言。但真正让它变得有用的读法是反过来如果某个语言连这个性质都不具备那它一定不是正则的。这是一个否定式的推论也是它 99% 的实战用法。所以你在教材里看到的绝大多数泵引理例题本质上都是反证法先假设语言正则然后找到一个字符串使得无论怎么切都泵不出去得到矛盾。把这个定位搞清楚之后证明本身的思路就顺了——我们要找的是那个“为什么正则语言的够长字符串一定会留下重复的痕迹”。2. 证明的骨架从 DFA 的状态轨迹里找那个重复点证明的起点是正则语言的定义。既然 L 是正则的它就一定被某个确定有限自动机 M (Q, Σ, δ, q₀, F) 接受其中 Q 是有限状态集δ 是转移函数q₀ 是初态F 是接受状态集。这是整个证明唯一能抓住的结构性事实后面所有推理都是从“Q 是有限的”这一个字眼里榨出来的。2.1 把一次完整匹配画成状态序列设 p |Q|也就是状态的总数。现在从 L 里随便挑一个长度不小于 p 的字符串 w写成一串字符 w a₁a₂…aₙ其中 n ≥ p。M 从 q₀ 出发读入 w每读一个字符就走一步于是产生一串状态r₀ q₀r₁ δ(r₀, a₁)r₂ δ(r₁, a₂)……rₙ δ(r_{n-1}, aₙ)因为 w ∈ L所以 rₙ ∈ F也就是走完之后停在接受状态上。这一串 r₀ 到 rₙ 就是这次匹配的“轨迹”一共 n 1 个状态每个都是 Q 里的元素。关键点来了轨迹的长度和状态集的大小之间出现了数量上的错位。因为 n ≥ p所以轨迹里至少有 p 1 个状态而状态集 Q 里一共只有 p 个不同的状态。p 1 个位置、p 种取值必然有重叠。2.2 鸽巢原理落在哪一段上如果只是说“某个状态重复了”这个重复可能发生在轨迹的末尾比如 r₃ 和 r₁₀₀ 相同那样我们切出来的 y 会很长|xy| ≤ p 就保不住了。所以必须把重复的位置限制在靠前的部分。正确的做法是只看轨迹的前 p 1 个状态r₀, r₁, r₂, …, r_p。这 p 1 个状态全部来自只有 p 个元素的 Q由鸽巢原理存在下标 i 和 j 满足 0 ≤ i j ≤ p 且 rᵢ rⱼ。注意 j 被卡在 p 以内这个上界是我们后面的约束条件能成立的唯一保障。选 i、j 的时候有两种常见写法一种是取 j 为最小的那个使 rⱼ 在前面出现过一次的下标另一种是直接说“存在一对”。两种都行但第一种写法更干净因为它能顺带保证 i 和 j 之间的段是“最短的重复”不过对本证明的三条约束来说并不是必需的。我在第一次写这个证明的时候就用了“存在一对”然后被要求说明为什么不影响结论——答案是三条约束都是不等式不是等式只要存在一对就够了不需要最优的那一对。2.3 x、y、z 三段切分的构造细节有了 i 和 j切分方式就自然浮出来了x a₁a₂…aᵢ前 i 个字符y a_{i1}a_{i2}…a_j从第 i1 个到第 j 个共 j − i 个字符z a_{j1}a_{j2}…aₙ剩下的一截。这样 xy 恰好对应轨迹从 r₀ 走到 r_j 的那一段而 x 对应从 r₀ 走到 rᵢ 的那一段。因为是按字符顺序切的w xyz 天然成立不需要额外验证。接下来要做的就是逐条核对那三个条件——这正是下一章要展开的部分。需要强调一点这个切分是由 M 的结构和内蕴的重复状态决定的对每个 w 都可能不一样但只要 w 足够长这样的切分就一定存在。这也是为什么 p 必须取状态数它保证了 w 的长度足以强迫轨迹出现重复。3. 逐条补齐三个约束条件是怎么被“撑住”的证明的骨架搭好之后剩下的工作是把三条约束逐一验证。这一步在教材里常常被一笔带过但恰恰是细节最容易出错的地方。我按顺序拆开讲。3.1 |y| ≥ 1 的来源i j 这个严格不等号y 的长度是 j − i。因为我们选取 i、j 时要求 i j所以 j − i ≥ 1也就是 y 至少包含一个字符。这个条件看起来平凡其实非常关键如果允许 y 为空整个引理就退化了。而 i j 这个严格要求是怎么保证的它来自鸽巢原理的结论形式——我们找的是两个不同位置上出现的相同状态位置不同对应的字符合数就至少差 1。这里有个常见的书写陷阱有人写成“存在 i ≤ j”这个等号会让整个证明失效。写的时候务必盯住这个小于号。3.2 |xy| ≤ p 为什么要卡前 p 个字符xy 的长度是 j。因为我们只在前 p 1 个状态 r₀…r_p 里找重复选出的 j ≤ p所以 |xy| j ≤ p。这条约束是整个引理中最“技术性”的它不做任何语义上的断言纯粹是把 y 的位置钉死在一个有限的窗口里。它为什么重要因为在反证时我们需要同时考虑“所有满足条件的切分方式”如果 y 可以出现在字符串任意靠后的位置这个集合就会变得难以穷举。|xy| ≤ p 把可能性压缩到前 p 个字符之内才让“对所有切分都失败”这种论证变得可行。你在做题时会强烈感受到这一点p 未知没关系只要我知道 y 一定落在前 p 个字符里我就能通过控制前 p 个字符的构成来锁死 y 的形态。3.3 i 取 0 和 i 取任意值归纳那一步的写法现在验证核心结论对所有 i ≥ 0xyⁱz ∈ L。证明的依据是 rᵢ rⱼ 这件事。从 rᵢ 出发读入 y会走到哪儿按定义y 是从第 i1 个字符到第 j 个字符从 rᵢ 读入 y 恰好走到 rⱼ。而 rⱼ rᵢ所以从 rᵢ 读入 y 之后仍然停在 rᵢ。这是一个“自环”——读一次 y 回到原点读两次还是回到原点。于是可以用归纳来写对 i 做归纳基础情况 i 0 时 xy⁰z xz从 r₀ 读入 x 到 rᵢ跳过 y再从 rᵢ 读入 z。因为 rᵢ rⱼ从 rᵢ 读 z 和从 rⱼ 读 z 到达的是同一个状态 rₙ而 rₙ ∈ F所以 xz ∈ L。归纳步假设 xyᵏz ∈ L那么从 r₀ 读 x 到 rᵢ重复 k1 次 y 后依然在 rᵢ再读 z 到 rₙ所以 xy^{k1}z ∈ L。如果想写得更紧凑可以直接用转移函数的扩展形式 δ*。因为 δ*(rᵢ, y) rⱼ rᵢ由扩展转移函数的复合性质对任意 k ≥ 0 都有 δ*(rᵢ, yᵏ) rᵢ。于是δ*(q₀, xyᵏz) δ*(δ*(q₀, x), yᵏz) δ*(rᵢ, yᵏz) δ*(δ*(rᵢ, yᵏ), z) δ*(rᵢ, z) rₙ ∈ F一行就结束了比归纳写法简洁得多。两种写法我都用过考试里写扩展转移的那一版更省时间但第一遍学的时候建议老老实实把归纳写出来能帮你把每一步的依赖关系看清楚。3.4 把证明写完整的标准格式模板汇总一下一份可以直接交作业的证明大概长这样设 L 正则取接受它的 DFA M令 p |Q|任取 w ∈ L 且 |w| ≥ p记 w a₁…aₙ定义状态轨迹 r₀…rₙ由鸽巢原理存在 0 ≤ i j ≤ p 使 rᵢ rⱼ令 x a₁…aᵢy a_{i1}…a_jz a_{j1}…aₙ验证 |y| j − i ≥ 1验证 |xy| j ≤ p验证 δ*(rᵢ, y) rᵢ 从而对所有 k ≥ 0 有 xyᵏz ∈ L。五步没有任何一步需要“灵感”。这也是泵引理证明的一个特点它不巧妙但每一步都可以被检查。我第一次自己独立写出来的时候卡在第 3 步的“为什么只看前 p1 个状态”后来想明白是为了给 |xy| ≤ p 留位置就通了。提示p 取状态数是最自然的选法但并不是唯一的。任何不小于状态数的常数都可以当泵长度因为 w 更长只会让重复更容易出现。实际写证明时用 p |Q| 最省事。4. 拿着泵引理去证“不正则”一场和假设的对抗证明完引理本身真正的主战场才开始。绝大多数场景下泵引理不是用来证明某个语言正则的而是用来证明某个语言不正则。这一章拆解这个用法重点讲清楚量词顺序因为这里是出错率最高的地方。4.1 反证法的量词顺序最容易翻车的地方泵引理的完整逻辑结构是这样的∃p∀w|w| ≥ p∃xyz∀i ≥ 0xyⁱz ∈ L做反证时要逐层否定否定之后量词翻转∀p∃w∀xyz∃i ≥ 0xyⁱz ∉ L翻译成人话就是p 由对手挑我们不知道具体数值w 由我们挑可以依赖 p 来构造xyz 由对手挑但必须满足 |y| ≥ 1 和 |xy| ≤ pi 由我们挑用来制造矛盾。这个角色分配非常关键。很多人在第一步就搞错了企图“对某个固定的 p 构造 w”或者“对某一个特定的切分方式证明矛盾”。正确的是w 可以依赖 p但必须对所有合法切分都成立切分方式是敌人的武器我们只能在切分确定之后挑 i。这就是为什么第 3.2 节里 |xy| ≤ p 那么重要——它把敌人的切分自由压缩到了一个可控范围。4.2 经典靶子 aⁿbⁿ 的完整推演拿最经典的语言 L {aⁿbⁿ | n ≥ 0} 走一遍。假设 L 正则则有泵长度 p。构造 w aᵖbᵖ显然 w ∈ L 且 |w| 2p ≥ p。现在考虑任意满足条件的切分 w xyz|y| ≥ 1|xy| ≤ p。因为 |xy| ≤ p而 w 的前 p 个字符全是 a所以 xy 完全落在 a 的区段里。又因为 |y| ≥ 1y 至少含一个 a而且 y 只含 a不含 b。写成 y aᵏk ≥ 1。取 i 0得到 xz。原来的字符串是 aᵖbᵖ删掉 y 里的 k 个 a 之后变成 a^{p−k}bᵖ。因为 k ≥ 1所以 p − k p两个区段的字符数不再相等xz ∉ L。而泵引理要求对所有 i 成立i 0 时就已经矛盾。假设不成立L 不是正则语言。整个过程里唯一的“选择”是 w 的构造和 i 的取值其余都是被动接受的。这套模板可以用在很多语言上只需要在构造 w 时让 p 附近的字符结构足够“干净”使得 y 的形态被唯一确定。4.3 换几个靶子平方长度、质数长度、回文串看几个常见的变形体会一下构造 w 的思路差异。语言 L {a^{n²} | n ≥ 0}长度的平方假设有泵长度 p取 w a^{p²}。切分后 y aᵏk ≥ 1 且 k ≤ p。泵一次得到 a^{p²k}。要制造矛盾需要 p² k 不是平方数。因为 (p1)² p² 2p 1而 k ≤ p 2p 1所以 p² k 严格落在 p² 和 (p1)² 之间不可能是平方数。取 i 2 即可。语言 L {aᵐ | m 是质数}这个用泵引理需要一点技巧因为质数的分布不像平方数那样容易卡区间。常见做法是取 w a^q其中 q 是大于等于 p 的质数质数有无穷多个一定取得到。切分后 y aᵏ1 ≤ k ≤ p。取 i q 1得到长度 q kq q(1 k)。因为 1 k ≥ 2这是一个合数矛盾。这个构造的漂亮之处在于 i 依赖于 q 而不只是依赖 p泵引理并没禁止我们这样做。语言 L {w | w 是回文串}取 w aᵖb aᵖ 或者 aᵖbᵖaᵖ 这类结构。以 w aᵖbaᵖ 为例|xy| ≤ p 迫使 xy 全在开头的 a 区段里y aᵏi 0 删掉之后从 p 个 a 变成 p−k 个 a两端不对称不再是回文。目标语言构造的 w关键观察选取的 iaⁿbⁿaᵖbᵖy 必落在前面 a 段内0a^(n²)a^{p²}p²k 落于相邻平方数之间2a^mm 为质数a^qq ≥ p 为质数q(1k) 是合数q1回文串aᵖbaᵖ删 a 后左右不对称0表格里这四种构造基本覆盖了初学阶段的常见题。它们的共同点是把 p 的信息编码进字符串的长度或前缀结构里让“y 一定落在某段纯字符里”这个事实变成武器。4.4 泵引理证明失败的两种典型情况第一种是把量词顺序搞反有人写“取一个切分 xyz然后发现某个 i 使 xyⁱz 不在 L”这就只否定了某一个切分不足以推翻结论。必须覆盖所有满足 |y| ≥ 1、|xy| ≤ p 的切分。判断自己有没有踩坑的方法很简单检查在论证过程中是否用到了 y 的具体取值如果只用到“y 落在这段区间内”这一性质那基本是对的如果假设了 y 等于某个具体字符串那大概率错了。第二种是构造的 w 长度不够或者结构不合适导致存在一种切分让所有 i 都成立。比如为了证明 aⁿbⁿ 不正则如果取 w aᵖbᵖ就很好但如果取 w aᵖbᵖcᵖ 去证明同样的结论虽然也不正则但论证会变得多余——不必要地引入 c 反而增加了切分的可能性。构造 w 的原则是越简洁越好只需恰好触发需要的那条约束。还有一个更深的坑泵引理的逆命题不成立。存在一些非正则语言它恰好满足泵引理的三个条件因此你再怎么努力也证不出矛盾。经典的反例是 L {aⁱbʲcᵏ | i, j, k ≥ 0 且 i 1 蕴含 j k} 这类带条件约束的语言验证过程相当繁琐。这里的直觉是泵引理的三条约束只作用在 w 的前 p 个字符和被泵的那一段上对于字符串更远处的结构它完全管不着。只要把“不规则”的部分设计得足够远、足够隐蔽泵引理的检查就够不着它。这个事实说明泵引理是一把有刻度的尺子不是万能判据。遇到证不出来的情况要么换 w要么就得动用 Myhill-Nerode 定理那种能给出充要条件的方法。5. 往上再走一层上下文无关语言的泵引理正则语言的泵引理搞清楚之后上下文无关语言CFL有对应的一个版本结构上像是一个“加强版”。很多教材把它放在下推自动机和文法化简之后讲标题里那个“★★”的说法通常也指向这一层值得单独展开。5.1 陈述形式的对比为什么变成五段切分CFL 的泵引理陈述是这样的若 L 是上下文无关语言则存在常数 p使得任意 w ∈ L 且 |w| ≥ p都可写成 w uvxyz 五段满足|vy| ≥ 1|vxy| ≤ p对所有 i ≥ 0uvⁱxyⁱz ∈ L。对比正则版本有两处变化。第一切分从三段变成五段。第二被泵的两段 v 和 y 必须同步泵且满足 v 和 y 不能同时为空。这些变化不是形式上的修饰而是来源于证明所依赖的结构不同。正则语言依赖的是状态轨迹上的一条路径重复的是一个状态上下文无关语言依赖的是语法树重复的是一个非终结符。树上有两个分支口所以被泵的是两段而不是一段。5.2 语法树里的重复变量证明思路拆解证明的大致流程是取一个生成 L 的乔姆斯基范式CNF文法 G它的变量非终结符个数记为 b。令 p 2^b。任取 w ∈ L 且 |w| ≥ p考虑 w 的一棵语法分析树。CNF 的特点是每个内部节点的分支数为 2要么 A → BC 的形式要么 A → a 的形式。对于一个每个内部节点最多有两个子节点的树高度为 h 的树最多有 2^(h−1) 个叶子。反过来说如果叶子数也就是 w 的长度不少于 2^b那么这棵树里一定存在一条从根到叶的路径路径上的非叶节点个数超过 b。路径上的每个非叶节点都对应一个变量而变量的种类只有 b 种由鸽巢原理这条路径上一定有两个节点标注了同一个变量记作 A其中靠上的那个叫“高 A”靠下的那个叫“低 A”。现在做切分。设高 A 生成的子串覆盖了 w 中从位置 a 到位置 b 的一段低 A 生成的子串覆盖了 w 中从位置 c 到位置 d 的一段且 [c, d] 被包在 [a, b] 里面。取 u w 在 [a, b] 左边的前缀v w 在 [a, c−1] 的部分x w 在 [c, d] 的部分y w 在 [d1, b] 的部分z w 在 [b, ...] 之后的部分。因为高 A 和低 A 是同一个变量低 A 能生成 x那么把低 A 替换成以高 A 为根的那棵子树就能多生成一次 v 和 y反过来把高 A 下面的那整棵子树替换成低 A 的子树就能少生成一次。这个“替换”动作可以无限次进行于是对所有 i ≥ 0 都有 uvⁱxyⁱz ∈ L。三条约束的验证|vy| ≥ 1 是因为高 A 和低 A 是两个不同的节点它们之间至少有一条产生式所以夹在中间的 v 和 y 不会同时为空。|vxy| ≤ p 则来自路径选取的方式——如果选的是那条“最长的路径”上最近的一对重复变量即不让中间再出现第三组重复那么低 A 生成的子树高度不超过 b 1叶子数不超过 2^b p而 |vxy| 正好不超过这棵子树能生成的串长。这个细节在书写时通常需要额外说明一句否则 |vxy| ≤ p 会站不住。5.3 用 aⁿbⁿcⁿ 走一遍完整流程拿 L {aⁿbⁿcⁿ | n ≥ 0} 做示范证明它不是上下文无关语言。假设 L 是 CFL有泵长度 p。取 w aᵖbᵖcᵖ满足 |w| ≥ p。任取合法切分 w uvxyz满足 |vy| ≥ 1 且 |vxy| ≤ p。因为 |vxy| ≤ p中间这一整段只有 p 个字符不可能同时覆盖超过两种字符区段的完整部分——具体地说vxy 不可能同时包含 a 和 c因为从第一个 a 到最后一个 c 至少隔着 p 个 a、p 个 b、p 个 c长度远超 p。所以 v 和 y 里最多只涉及 a、b、c 中的两种。现在取 i 2。两端 v 和 y 被复制一次只用其中一种或两种字符的数量增加另外那种字符的数量保持不变。结果是三种字符的数量不再相等uv²xy²z ∉ L矛盾。假设不成立L 不是上下文无关语言。注意这个论证比正则版本“宽松”一些我们不需要精确说明 y 落在哪一段只需要说明 |vxy| ≤ p 让它无法横跨三种字符这就够了。这是 CFL 泵引理在做题时的一个显著特点——约束更好用因为 p 的窗口限制更强了。5.4 泵引理在 CFL 上的局限它证明不了什么和正则版本一样CFL 泵引理也只是一条必要条件不能反过来用。存在非上下文无关但满足这条引理的语言而且数量比正则那边更多因为 CFL 的结构更复杂泵引理能捕捉到的“规律性”更少。实际做题时的经验是如果一条语言看起来“结构很规整只是某个计数关系不对”CFL 泵引理通常够用如果语言里有两三处互相纠缠的依赖关系比如 {aⁱbʲcᵏ | i j k} 这种直接上泵引理会很别扭往往需要配合 Ogden 引理对泵的位置施加额外标记才能拿下。这个工具已经超出了本文的范围但值得知道它的存在——当泵引理反复卡壳时不是你写错了是工具本身的刻度不够细。还有一个容易混淆的点乔姆斯基范式是证明 CFL 泵引理的中间手段但并不是每个 CFL 的生成文法都已经处于 CNF。做证明题时我们要先做一步转化把任给的文法转成 CNF这步转化的可行性由文法化简那一章保证消除空产生式、消除单位产生式、消除无用符号。这一步在标准证明里常常被省略成一句“不妨设 G 是 CNF 文法”但在自己推导的时候值得走一遍否则 p 2^b 这个取值会显得凭空冒出来。6. 我踩过的几个坑和一点私人经验关于这个主题我自己在学的过程中遇到过几个具体的问题写出来给后来人省点时间。第一个是关于 p 的理解。我一开始总想算出 p 的具体数值觉得不给出具体数字的证明“不够硬”。后来才意识到p 的存在性本身就是全部——反证里我们只是在假设 p 存在的情况下工作从不需要用到它的数值。凡是需要知道 p 具体是多少的证明反而是走错了方向。第二个是关于 w 的构造。我早期做题习惯直接套 aᵖbᵖ遇到稍微复杂的语言就卡壳。后来总结出的方法是先把语言“不规则的那部分”写出来再想怎么让这段结构在本该被 y 覆盖的窗口里暴露出来。比如平方长度语言的关键是“相邻平方数之间有间隙”质数长度语言的关键是“q 乘以大于 1 的数是合数”回文串的关键是“删掉一段后左右不对称”。先找到那个破绽再决定 w 长什么样比先构造 w 再找破绽效率高得多。第三个是关于书写规范。前面提过量词顺序我再强调一次写反证时习惯性地把“对所有切分”这四个字写在纸上提醒自己论证的对象是全称集合。我见过太多人在这一步失手包括我自己在第一次考试时——那道题我取了一个特定切分证明了矛盾以为大功告成结果只拿到一半分数。最后分享一个自查技巧证完之后倒回去看一遍检查自己的论证里有没有出现“假设 y 等于某个具体串”这样的表述。如果没有只用到“y 落在某个区间内”和“|y| ≥ 1”那这份证明基本就是稳的。这个检查让我在后续几次练习里避开了不少隐藏错误。 泵引理证明全解：DFA状态重复、三条约束与反证证不正则
1. 泵引理在证明什么把“有限状态”翻译成“必然重复”几乎所有讲计算理论的课程都会把泵引理Pumping Lemma放在正则语言那一章的后半段但它出现的时机很尴尬前面刚学完 DFA、NFA、正则表达式三者的等价性后面马上要进入上下文无关文法和下推自动机。很多人囫囵吞枣地背下三个条件考试能套着用但一到“为什么这三个条件就够用”就卡住。我自己第一次看的时候也是这样直到把它的证明拆成“有限个状态 一条足够长的路径”这两件事才真正把它当成一个可以随手复现的工具而不是需要死记的公式。先把结论摆出来。设 L 是一个正则语言那么存在一个常数 p通常叫泵长度pumping length使得 L 中任意长度不小于 p 的字符串 w都可以切成三段 w xyz并且同时满足三条|y| ≥ 1也就是被“泵”的那一段不能是空串|xy| ≤ p也就是被泵的那一段必须出现在足够靠前的位置对所有 i ≥ 0xyⁱz 都属于 L。注意第三条里的 i 是从 0 开始的非负整数包括 i 0也就是把 y 整个删掉。这一点在后续用它做反证时是主战场因为 i 0 往往是最容易构造出矛盾的取值。1.1 三个条件各自承担的角色这三条不是随手凑出来的每一条都在为后续的“反证”服务。|y| ≥ 1 保证了泵这个动作真的改变了字符串如果允许 y 是空串那 xyⁱz 永远等于原串条件就变成了一句废话任何语言都满足。|xy| ≤ p 保证了被泵的那一段落在字符串前面的有限窗口里这是证明过程中“鸽巢原理”能够生效的直接后果也是后面构造矛盾时我们唯一能确定位置的依据。第三条则是结论本身它把“可以无限次重复”这件事写成了对所有 i 成立的全称命题——正是这个全称量词给了我们挑选某个特定 i 来制造反例的自由。换个角度理解前两条是在描述“y 长什么样、在哪”第三条是在描述“y 能干什么”。做证明题时前两条限制你只能在前 p 个字符里找 y第三条给你无限的火力去挑 i。1.2 一个容易被忽略的前提语言必须是正则的泵引理的陈述里“L 是正则语言”是前提不是结论。这意味着它是一条必要条件只在“正则 ⇒ 可泵”这个方向成立。很多人做题时下意识地反着用看到某个语言可以泵就说它正则这是典型的逻辑倒错。正则有泵引理但可泵不等于正则后面第 4 章会专门讲这件事。另外p 是一个与具体字符串无关的常数只取决于语言本身——更准确地说取决于接受这个语言的 DFA 的状态数。它不需要你算出来具体是多少在反证过程中我们只用到“p 存在”这一事实然后可以假设 p 任意大构造一个比 p 更长的字符串来触发矛盾。1.3 反向读它其实是一个“非存在性”工具正着读泵引理说的是一件所有正则语言都具备的性质是一句“有”的断言。但真正让它变得有用的读法是反过来如果某个语言连这个性质都不具备那它一定不是正则的。这是一个否定式的推论也是它 99% 的实战用法。所以你在教材里看到的绝大多数泵引理例题本质上都是反证法先假设语言正则然后找到一个字符串使得无论怎么切都泵不出去得到矛盾。把这个定位搞清楚之后证明本身的思路就顺了——我们要找的是那个“为什么正则语言的够长字符串一定会留下重复的痕迹”。2. 证明的骨架从 DFA 的状态轨迹里找那个重复点证明的起点是正则语言的定义。既然 L 是正则的它就一定被某个确定有限自动机 M (Q, Σ, δ, q₀, F) 接受其中 Q 是有限状态集δ 是转移函数q₀ 是初态F 是接受状态集。这是整个证明唯一能抓住的结构性事实后面所有推理都是从“Q 是有限的”这一个字眼里榨出来的。2.1 把一次完整匹配画成状态序列设 p |Q|也就是状态的总数。现在从 L 里随便挑一个长度不小于 p 的字符串 w写成一串字符 w a₁a₂…aₙ其中 n ≥ p。M 从 q₀ 出发读入 w每读一个字符就走一步于是产生一串状态r₀ q₀r₁ δ(r₀, a₁)r₂ δ(r₁, a₂)……rₙ δ(r_{n-1}, aₙ)因为 w ∈ L所以 rₙ ∈ F也就是走完之后停在接受状态上。这一串 r₀ 到 rₙ 就是这次匹配的“轨迹”一共 n 1 个状态每个都是 Q 里的元素。关键点来了轨迹的长度和状态集的大小之间出现了数量上的错位。因为 n ≥ p所以轨迹里至少有 p 1 个状态而状态集 Q 里一共只有 p 个不同的状态。p 1 个位置、p 种取值必然有重叠。2.2 鸽巢原理落在哪一段上如果只是说“某个状态重复了”这个重复可能发生在轨迹的末尾比如 r₃ 和 r₁₀₀ 相同那样我们切出来的 y 会很长|xy| ≤ p 就保不住了。所以必须把重复的位置限制在靠前的部分。正确的做法是只看轨迹的前 p 1 个状态r₀, r₁, r₂, …, r_p。这 p 1 个状态全部来自只有 p 个元素的 Q由鸽巢原理存在下标 i 和 j 满足 0 ≤ i j ≤ p 且 rᵢ rⱼ。注意 j 被卡在 p 以内这个上界是我们后面的约束条件能成立的唯一保障。选 i、j 的时候有两种常见写法一种是取 j 为最小的那个使 rⱼ 在前面出现过一次的下标另一种是直接说“存在一对”。两种都行但第一种写法更干净因为它能顺带保证 i 和 j 之间的段是“最短的重复”不过对本证明的三条约束来说并不是必需的。我在第一次写这个证明的时候就用了“存在一对”然后被要求说明为什么不影响结论——答案是三条约束都是不等式不是等式只要存在一对就够了不需要最优的那一对。2.3 x、y、z 三段切分的构造细节有了 i 和 j切分方式就自然浮出来了x a₁a₂…aᵢ前 i 个字符y a_{i1}a_{i2}…a_j从第 i1 个到第 j 个共 j − i 个字符z a_{j1}a_{j2}…aₙ剩下的一截。这样 xy 恰好对应轨迹从 r₀ 走到 r_j 的那一段而 x 对应从 r₀ 走到 rᵢ 的那一段。因为是按字符顺序切的w xyz 天然成立不需要额外验证。接下来要做的就是逐条核对那三个条件——这正是下一章要展开的部分。需要强调一点这个切分是由 M 的结构和内蕴的重复状态决定的对每个 w 都可能不一样但只要 w 足够长这样的切分就一定存在。这也是为什么 p 必须取状态数它保证了 w 的长度足以强迫轨迹出现重复。3. 逐条补齐三个约束条件是怎么被“撑住”的证明的骨架搭好之后剩下的工作是把三条约束逐一验证。这一步在教材里常常被一笔带过但恰恰是细节最容易出错的地方。我按顺序拆开讲。3.1 |y| ≥ 1 的来源i j 这个严格不等号y 的长度是 j − i。因为我们选取 i、j 时要求 i j所以 j − i ≥ 1也就是 y 至少包含一个字符。这个条件看起来平凡其实非常关键如果允许 y 为空整个引理就退化了。而 i j 这个严格要求是怎么保证的它来自鸽巢原理的结论形式——我们找的是两个不同位置上出现的相同状态位置不同对应的字符合数就至少差 1。这里有个常见的书写陷阱有人写成“存在 i ≤ j”这个等号会让整个证明失效。写的时候务必盯住这个小于号。3.2 |xy| ≤ p 为什么要卡前 p 个字符xy 的长度是 j。因为我们只在前 p 1 个状态 r₀…r_p 里找重复选出的 j ≤ p所以 |xy| j ≤ p。这条约束是整个引理中最“技术性”的它不做任何语义上的断言纯粹是把 y 的位置钉死在一个有限的窗口里。它为什么重要因为在反证时我们需要同时考虑“所有满足条件的切分方式”如果 y 可以出现在字符串任意靠后的位置这个集合就会变得难以穷举。|xy| ≤ p 把可能性压缩到前 p 个字符之内才让“对所有切分都失败”这种论证变得可行。你在做题时会强烈感受到这一点p 未知没关系只要我知道 y 一定落在前 p 个字符里我就能通过控制前 p 个字符的构成来锁死 y 的形态。3.3 i 取 0 和 i 取任意值归纳那一步的写法现在验证核心结论对所有 i ≥ 0xyⁱz ∈ L。证明的依据是 rᵢ rⱼ 这件事。从 rᵢ 出发读入 y会走到哪儿按定义y 是从第 i1 个字符到第 j 个字符从 rᵢ 读入 y 恰好走到 rⱼ。而 rⱼ rᵢ所以从 rᵢ 读入 y 之后仍然停在 rᵢ。这是一个“自环”——读一次 y 回到原点读两次还是回到原点。于是可以用归纳来写对 i 做归纳基础情况 i 0 时 xy⁰z xz从 r₀ 读入 x 到 rᵢ跳过 y再从 rᵢ 读入 z。因为 rᵢ rⱼ从 rᵢ 读 z 和从 rⱼ 读 z 到达的是同一个状态 rₙ而 rₙ ∈ F所以 xz ∈ L。归纳步假设 xyᵏz ∈ L那么从 r₀ 读 x 到 rᵢ重复 k1 次 y 后依然在 rᵢ再读 z 到 rₙ所以 xy^{k1}z ∈ L。如果想写得更紧凑可以直接用转移函数的扩展形式 δ*。因为 δ*(rᵢ, y) rⱼ rᵢ由扩展转移函数的复合性质对任意 k ≥ 0 都有 δ*(rᵢ, yᵏ) rᵢ。于是δ*(q₀, xyᵏz) δ*(δ*(q₀, x), yᵏz) δ*(rᵢ, yᵏz) δ*(δ*(rᵢ, yᵏ), z) δ*(rᵢ, z) rₙ ∈ F一行就结束了比归纳写法简洁得多。两种写法我都用过考试里写扩展转移的那一版更省时间但第一遍学的时候建议老老实实把归纳写出来能帮你把每一步的依赖关系看清楚。3.4 把证明写完整的标准格式模板汇总一下一份可以直接交作业的证明大概长这样设 L 正则取接受它的 DFA M令 p |Q|任取 w ∈ L 且 |w| ≥ p记 w a₁…aₙ定义状态轨迹 r₀…rₙ由鸽巢原理存在 0 ≤ i j ≤ p 使 rᵢ rⱼ令 x a₁…aᵢy a_{i1}…a_jz a_{j1}…aₙ验证 |y| j − i ≥ 1验证 |xy| j ≤ p验证 δ*(rᵢ, y) rᵢ 从而对所有 k ≥ 0 有 xyᵏz ∈ L。五步没有任何一步需要“灵感”。这也是泵引理证明的一个特点它不巧妙但每一步都可以被检查。我第一次自己独立写出来的时候卡在第 3 步的“为什么只看前 p1 个状态”后来想明白是为了给 |xy| ≤ p 留位置就通了。提示p 取状态数是最自然的选法但并不是唯一的。任何不小于状态数的常数都可以当泵长度因为 w 更长只会让重复更容易出现。实际写证明时用 p |Q| 最省事。4. 拿着泵引理去证“不正则”一场和假设的对抗证明完引理本身真正的主战场才开始。绝大多数场景下泵引理不是用来证明某个语言正则的而是用来证明某个语言不正则。这一章拆解这个用法重点讲清楚量词顺序因为这里是出错率最高的地方。4.1 反证法的量词顺序最容易翻车的地方泵引理的完整逻辑结构是这样的∃p∀w|w| ≥ p∃xyz∀i ≥ 0xyⁱz ∈ L做反证时要逐层否定否定之后量词翻转∀p∃w∀xyz∃i ≥ 0xyⁱz ∉ L翻译成人话就是p 由对手挑我们不知道具体数值w 由我们挑可以依赖 p 来构造xyz 由对手挑但必须满足 |y| ≥ 1 和 |xy| ≤ pi 由我们挑用来制造矛盾。这个角色分配非常关键。很多人在第一步就搞错了企图“对某个固定的 p 构造 w”或者“对某一个特定的切分方式证明矛盾”。正确的是w 可以依赖 p但必须对所有合法切分都成立切分方式是敌人的武器我们只能在切分确定之后挑 i。这就是为什么第 3.2 节里 |xy| ≤ p 那么重要——它把敌人的切分自由压缩到了一个可控范围。4.2 经典靶子 aⁿbⁿ 的完整推演拿最经典的语言 L {aⁿbⁿ | n ≥ 0} 走一遍。假设 L 正则则有泵长度 p。构造 w aᵖbᵖ显然 w ∈ L 且 |w| 2p ≥ p。现在考虑任意满足条件的切分 w xyz|y| ≥ 1|xy| ≤ p。因为 |xy| ≤ p而 w 的前 p 个字符全是 a所以 xy 完全落在 a 的区段里。又因为 |y| ≥ 1y 至少含一个 a而且 y 只含 a不含 b。写成 y aᵏk ≥ 1。取 i 0得到 xz。原来的字符串是 aᵖbᵖ删掉 y 里的 k 个 a 之后变成 a^{p−k}bᵖ。因为 k ≥ 1所以 p − k p两个区段的字符数不再相等xz ∉ L。而泵引理要求对所有 i 成立i 0 时就已经矛盾。假设不成立L 不是正则语言。整个过程里唯一的“选择”是 w 的构造和 i 的取值其余都是被动接受的。这套模板可以用在很多语言上只需要在构造 w 时让 p 附近的字符结构足够“干净”使得 y 的形态被唯一确定。4.3 换几个靶子平方长度、质数长度、回文串看几个常见的变形体会一下构造 w 的思路差异。语言 L {a^{n²} | n ≥ 0}长度的平方假设有泵长度 p取 w a^{p²}。切分后 y aᵏk ≥ 1 且 k ≤ p。泵一次得到 a^{p²k}。要制造矛盾需要 p² k 不是平方数。因为 (p1)² p² 2p 1而 k ≤ p 2p 1所以 p² k 严格落在 p² 和 (p1)² 之间不可能是平方数。取 i 2 即可。语言 L {aᵐ | m 是质数}这个用泵引理需要一点技巧因为质数的分布不像平方数那样容易卡区间。常见做法是取 w a^q其中 q 是大于等于 p 的质数质数有无穷多个一定取得到。切分后 y aᵏ1 ≤ k ≤ p。取 i q 1得到长度 q kq q(1 k)。因为 1 k ≥ 2这是一个合数矛盾。这个构造的漂亮之处在于 i 依赖于 q 而不只是依赖 p泵引理并没禁止我们这样做。语言 L {w | w 是回文串}取 w aᵖb aᵖ 或者 aᵖbᵖaᵖ 这类结构。以 w aᵖbaᵖ 为例|xy| ≤ p 迫使 xy 全在开头的 a 区段里y aᵏi 0 删掉之后从 p 个 a 变成 p−k 个 a两端不对称不再是回文。目标语言构造的 w关键观察选取的 iaⁿbⁿaᵖbᵖy 必落在前面 a 段内0a^(n²)a^{p²}p²k 落于相邻平方数之间2a^mm 为质数a^qq ≥ p 为质数q(1k) 是合数q1回文串aᵖbaᵖ删 a 后左右不对称0表格里这四种构造基本覆盖了初学阶段的常见题。它们的共同点是把 p 的信息编码进字符串的长度或前缀结构里让“y 一定落在某段纯字符里”这个事实变成武器。4.4 泵引理证明失败的两种典型情况第一种是把量词顺序搞反有人写“取一个切分 xyz然后发现某个 i 使 xyⁱz 不在 L”这就只否定了某一个切分不足以推翻结论。必须覆盖所有满足 |y| ≥ 1、|xy| ≤ p 的切分。判断自己有没有踩坑的方法很简单检查在论证过程中是否用到了 y 的具体取值如果只用到“y 落在这段区间内”这一性质那基本是对的如果假设了 y 等于某个具体字符串那大概率错了。第二种是构造的 w 长度不够或者结构不合适导致存在一种切分让所有 i 都成立。比如为了证明 aⁿbⁿ 不正则如果取 w aᵖbᵖ就很好但如果取 w aᵖbᵖcᵖ 去证明同样的结论虽然也不正则但论证会变得多余——不必要地引入 c 反而增加了切分的可能性。构造 w 的原则是越简洁越好只需恰好触发需要的那条约束。还有一个更深的坑泵引理的逆命题不成立。存在一些非正则语言它恰好满足泵引理的三个条件因此你再怎么努力也证不出矛盾。经典的反例是 L {aⁱbʲcᵏ | i, j, k ≥ 0 且 i 1 蕴含 j k} 这类带条件约束的语言验证过程相当繁琐。这里的直觉是泵引理的三条约束只作用在 w 的前 p 个字符和被泵的那一段上对于字符串更远处的结构它完全管不着。只要把“不规则”的部分设计得足够远、足够隐蔽泵引理的检查就够不着它。这个事实说明泵引理是一把有刻度的尺子不是万能判据。遇到证不出来的情况要么换 w要么就得动用 Myhill-Nerode 定理那种能给出充要条件的方法。5. 往上再走一层上下文无关语言的泵引理正则语言的泵引理搞清楚之后上下文无关语言CFL有对应的一个版本结构上像是一个“加强版”。很多教材把它放在下推自动机和文法化简之后讲标题里那个“★★”的说法通常也指向这一层值得单独展开。5.1 陈述形式的对比为什么变成五段切分CFL 的泵引理陈述是这样的若 L 是上下文无关语言则存在常数 p使得任意 w ∈ L 且 |w| ≥ p都可写成 w uvxyz 五段满足|vy| ≥ 1|vxy| ≤ p对所有 i ≥ 0uvⁱxyⁱz ∈ L。对比正则版本有两处变化。第一切分从三段变成五段。第二被泵的两段 v 和 y 必须同步泵且满足 v 和 y 不能同时为空。这些变化不是形式上的修饰而是来源于证明所依赖的结构不同。正则语言依赖的是状态轨迹上的一条路径重复的是一个状态上下文无关语言依赖的是语法树重复的是一个非终结符。树上有两个分支口所以被泵的是两段而不是一段。5.2 语法树里的重复变量证明思路拆解证明的大致流程是取一个生成 L 的乔姆斯基范式CNF文法 G它的变量非终结符个数记为 b。令 p 2^b。任取 w ∈ L 且 |w| ≥ p考虑 w 的一棵语法分析树。CNF 的特点是每个内部节点的分支数为 2要么 A → BC 的形式要么 A → a 的形式。对于一个每个内部节点最多有两个子节点的树高度为 h 的树最多有 2^(h−1) 个叶子。反过来说如果叶子数也就是 w 的长度不少于 2^b那么这棵树里一定存在一条从根到叶的路径路径上的非叶节点个数超过 b。路径上的每个非叶节点都对应一个变量而变量的种类只有 b 种由鸽巢原理这条路径上一定有两个节点标注了同一个变量记作 A其中靠上的那个叫“高 A”靠下的那个叫“低 A”。现在做切分。设高 A 生成的子串覆盖了 w 中从位置 a 到位置 b 的一段低 A 生成的子串覆盖了 w 中从位置 c 到位置 d 的一段且 [c, d] 被包在 [a, b] 里面。取 u w 在 [a, b] 左边的前缀v w 在 [a, c−1] 的部分x w 在 [c, d] 的部分y w 在 [d1, b] 的部分z w 在 [b, ...] 之后的部分。因为高 A 和低 A 是同一个变量低 A 能生成 x那么把低 A 替换成以高 A 为根的那棵子树就能多生成一次 v 和 y反过来把高 A 下面的那整棵子树替换成低 A 的子树就能少生成一次。这个“替换”动作可以无限次进行于是对所有 i ≥ 0 都有 uvⁱxyⁱz ∈ L。三条约束的验证|vy| ≥ 1 是因为高 A 和低 A 是两个不同的节点它们之间至少有一条产生式所以夹在中间的 v 和 y 不会同时为空。|vxy| ≤ p 则来自路径选取的方式——如果选的是那条“最长的路径”上最近的一对重复变量即不让中间再出现第三组重复那么低 A 生成的子树高度不超过 b 1叶子数不超过 2^b p而 |vxy| 正好不超过这棵子树能生成的串长。这个细节在书写时通常需要额外说明一句否则 |vxy| ≤ p 会站不住。5.3 用 aⁿbⁿcⁿ 走一遍完整流程拿 L {aⁿbⁿcⁿ | n ≥ 0} 做示范证明它不是上下文无关语言。假设 L 是 CFL有泵长度 p。取 w aᵖbᵖcᵖ满足 |w| ≥ p。任取合法切分 w uvxyz满足 |vy| ≥ 1 且 |vxy| ≤ p。因为 |vxy| ≤ p中间这一整段只有 p 个字符不可能同时覆盖超过两种字符区段的完整部分——具体地说vxy 不可能同时包含 a 和 c因为从第一个 a 到最后一个 c 至少隔着 p 个 a、p 个 b、p 个 c长度远超 p。所以 v 和 y 里最多只涉及 a、b、c 中的两种。现在取 i 2。两端 v 和 y 被复制一次只用其中一种或两种字符的数量增加另外那种字符的数量保持不变。结果是三种字符的数量不再相等uv²xy²z ∉ L矛盾。假设不成立L 不是上下文无关语言。注意这个论证比正则版本“宽松”一些我们不需要精确说明 y 落在哪一段只需要说明 |vxy| ≤ p 让它无法横跨三种字符这就够了。这是 CFL 泵引理在做题时的一个显著特点——约束更好用因为 p 的窗口限制更强了。5.4 泵引理在 CFL 上的局限它证明不了什么和正则版本一样CFL 泵引理也只是一条必要条件不能反过来用。存在非上下文无关但满足这条引理的语言而且数量比正则那边更多因为 CFL 的结构更复杂泵引理能捕捉到的“规律性”更少。实际做题时的经验是如果一条语言看起来“结构很规整只是某个计数关系不对”CFL 泵引理通常够用如果语言里有两三处互相纠缠的依赖关系比如 {aⁱbʲcᵏ | i j k} 这种直接上泵引理会很别扭往往需要配合 Ogden 引理对泵的位置施加额外标记才能拿下。这个工具已经超出了本文的范围但值得知道它的存在——当泵引理反复卡壳时不是你写错了是工具本身的刻度不够细。还有一个容易混淆的点乔姆斯基范式是证明 CFL 泵引理的中间手段但并不是每个 CFL 的生成文法都已经处于 CNF。做证明题时我们要先做一步转化把任给的文法转成 CNF这步转化的可行性由文法化简那一章保证消除空产生式、消除单位产生式、消除无用符号。这一步在标准证明里常常被省略成一句“不妨设 G 是 CNF 文法”但在自己推导的时候值得走一遍否则 p 2^b 这个取值会显得凭空冒出来。6. 我踩过的几个坑和一点私人经验关于这个主题我自己在学的过程中遇到过几个具体的问题写出来给后来人省点时间。第一个是关于 p 的理解。我一开始总想算出 p 的具体数值觉得不给出具体数字的证明“不够硬”。后来才意识到p 的存在性本身就是全部——反证里我们只是在假设 p 存在的情况下工作从不需要用到它的数值。凡是需要知道 p 具体是多少的证明反而是走错了方向。第二个是关于 w 的构造。我早期做题习惯直接套 aᵖbᵖ遇到稍微复杂的语言就卡壳。后来总结出的方法是先把语言“不规则的那部分”写出来再想怎么让这段结构在本该被 y 覆盖的窗口里暴露出来。比如平方长度语言的关键是“相邻平方数之间有间隙”质数长度语言的关键是“q 乘以大于 1 的数是合数”回文串的关键是“删掉一段后左右不对称”。先找到那个破绽再决定 w 长什么样比先构造 w 再找破绽效率高得多。第三个是关于书写规范。前面提过量词顺序我再强调一次写反证时习惯性地把“对所有切分”这四个字写在纸上提醒自己论证的对象是全称集合。我见过太多人在这一步失手包括我自己在第一次考试时——那道题我取了一个特定切分证明了矛盾以为大功告成结果只拿到一半分数。最后分享一个自查技巧证完之后倒回去看一遍检查自己的论证里有没有出现“假设 y 等于某个具体串”这样的表述。如果没有只用到“y 落在某个区间内”和“|y| ≥ 1”那这份证明基本就是稳的。这个检查让我在后续几次练习里避开了不少隐藏错误。