非上下文无关语言：泵引理与CNF证明经典例题详解

非上下文无关语言

问题来了：是否存在不是上下文无关的语言？例如 $L = \{a^n b^n c^n \mid n\ge 0\}$ 呢？
答案是： 这个 $L$ 不是上下文无关语言。

直观看，判断成员关系必须同时比较 $a$、$b$、$c$ 三类符号的数量。单栈最多擅长匹配一组依赖（如 $a$ 与 $b$），却无法同时处理两组比较。把这种直觉严格化的工具就是 CFL 的 pumping lemma（抽引引理）。

CFL 抽引引理（非形式化）

对 CFL 中任意足够长的串 $z$，总能找到两段相近的子串，可以“同时抽引”且结果仍然留在 $L$ 中。

CFL 抽引引理（形式化）

如果 $L$ 是 CFL，则存在一个抽引长度 $p$，使得对任意 $z \in L$ 且 $|z| \ge p$，都可以将 $z$ 分解为
$z = uvwxy$，并且满足：

1. $|vwx| \le p$
2. $|vx| > 0$
3. 对所有 $i \ge 0$，$uv^i wx^i y \in L$

两个抽引引理对比

• 对 CFL：$z = uvwxy$，同时抽引 $v$ 与 $x$。
• 对 正则语言：$z = uvw$，只抽引 $v$。

两者都要求存在抽引长度 $p$，抽引后的字符串仍属于原语言。

乔姆斯基范式（CNF）

命题：对任意非空 CFL $L$，都存在一个文法 $G$，使得 $L(G) = L$，且每条规则属于以下形式之一：

1. $A \to a$，其中 $a \in \Sigma$
2. $A \to BC$，且 $B$、$C$ 都不是开始符号
3. $S \to \varepsilon$（仅当 $\varepsilon \in L$ 时）

满足这种受限规则形态的文法称为 CNF 文法。

证明思路

设 $G$ 为 CNF 且 $L(G)=L$，取一个充分长的串 $z \in L$。
因为 $z \in L$，它必有一棵语法树；在 CNF 下这棵树是二叉的。
若 $z$ 足够长，树就足够高，因此某条根到叶子的路径上必然有变量重复（鸽巢原理）。
利用这个重复变量，可将 $z$ 划分为 $u, v, w, x, y$。

抽引操作

通过删除一层重复结构（泵下）或复制一层（泵上），就能得到形如 $uv^i wx^i y$ 的字符串。于是对每个 $i \ge 0$，$uv^i wx^i y$ 都存在对应的语法树。

抽引引理证明：高语法树的存在性

设 $G$ 为 CNF，有 $k$ 个变量，且 $L(G) = L$。取 $p = 2^k$。
对任意 $z \in L$ 且 $|z| \ge p$，$z$ 的语法树高度至少为 $k+1$。
原因：高度为 $h$ 的二叉树最多有 $2^{h-1}$ 个叶子，而 $|z|$ 正好等于叶子数。所以当 $|z| \ge 2^k$ 时，必有 $h \ge k+1$。

抽引引理证明：$u,v,w,x,y$ 的性质

在同一路径上选取重复变量 $n_1$ 与 $n_2$。
$n_1$ 对应的产出 $vwx$ 的长度可以被 $p$ 约束，即 $|vwx| \le p$。
因为 $n_1 \ne n_2$，且此时不会出现导致长度塌缩的空产生式或单元产生式，故 $|vx| > 0$。

抽引引理证明：对字符串抽引

由语法树分解可得：$S \Rightarrow^* uAy$，$A \Rightarrow^* vAx$，且 $A \Rightarrow^* w$。
组合起来：对所有 $i \ge 0$，$S \Rightarrow^* uv^i wx^i y$。
因此 $uv^i wx^i y \in L$ 对所有 $i \ge 0$ 成立。

---

例题 I：证明 $L = \{a^n b^n c^n \mid n\ge 0\}$ 不是 CFL

命题：$L = \{a^n b^n c^n \mid n \ge 0\}$ 不是上下文无关语言。  

证明：
反设 $L$ 是 CFL，令 $p$ 为抽引长度。
取 $z = a^p b^p c^p \in L$。由于 $|z| \ge p$，按引理可分解 $z = uvwxy$ 且满足约束。
因为 $|vwx| \le p$，$vwx$ 不可能同时跨越 $a,b,c$ 三个区段。
取 $i=0$ 或 $i=2$ 抽引，都会破坏三类符号的相等数量，得到的串不在 $L$ 中，矛盾。
故 $L$ 不是 CFL。

---

例题 II：证明 $L = \{a^m b^n c^m d^n \mid m,n\ge 0\}$ 不是 CFL

（该语言的约束可记作 $L_{a=c \land b=d}$，即“$a$ 与 $c$ 同数、$b$ 与 $d$ 同数”。这里用 $m,n$ 以免与下文抽引指数混淆。）

命题：$L = \{a^m b^n c^m d^n \mid m,n \ge 0\}$ 不是 CFL。  

证明：
假设 $L$ 是上下文无关语言，设 $p$ 为抽引长度。
取 $z = a^p b^p c^p d^p \in L$。
由抽引引理，$z = uvwxy$，满足 $|vwx| \le p$、$|vx| > 0$，且对任意抽引指数 $t \ge 0$ 有 $uv^t wx^t y \in L$。
因为 $|vwx| \le p$，被抽引窗口 $vwx$ 不可能同时覆盖“$a$ 与 $c$”和“$b$ 与 $d$”两组跨块配对。
取 $t = 0$（泵下），至少破坏 $\#a = \#c$ 或 $\#b = \#d$ 中的一组，故 $uv^0 wx^0 y \notin L$，矛盾。
因此 $L$ 不是 CFL。

---

例题 III：错误证明与正确做法

命题：$E = \{ ww \mid w \in \{0,1\}^* \}$ 不是 CFL。

常见错误证明

一种常见错误是：只选定 $z$ 的某一种特定分解，然后论证该分解无法泵送。
但 CFL 抽引引理说的是：对 任意 足够长的 $z \in L$，存在 某种有效分解可以泵送。
要证伪 CFL 性质，必须证明 所有可能的分解都会失败，而不能只否定自己挑的一种。

正确证明

假设 $E$ 是 CFL，令 $p$ 为抽引长度。
选择 $z = 0^p 1^p 0^p 1^p \in E$。
对任意满足 $|vwx| \le p$ 且 $|vx| > 0$ 的分解 $z = uvwxy$，分类讨论 $vwx$ 的位置：

• 若 $vwx$ 完全落在前半段或完全落在后半段：泵送会只改变其中一半而不改变另一半，结果不再是 $ww$ 形式。
• 若 $vwx$ 跨越 $z$ 的中点：泵下（$i=0$）将得到形如 $0^p 1^i 0^j 1^p$ 的串，其中 $i \ne p$ 或 $j \ne p$。前后两半不再相同，故 $uv^0 wx^0 y \notin E$。

所有情况均导致矛盾，因此 $E$ 不是 CFL。这种对任意分解全覆盖的论证，才是正确使用泵引理的标准写法。

本文是一次典型的计算理论复习笔记。在 云栈社区 的技术论坛中，你可以找到更多关于形式语言与 自动机理论 的深度讨论和资源共享。