2_上下文无关语言2.3.ZH解释

这段话是本章节的引言，起到了提纲挈领的作用。它告诉我们本节的核心目标：学习一种证明工具，用来判断一个语言不是上下文无关语言。

1. 核心任务：本节要解决的问题是“如何证明一个语言不是上下文无关语言（Context-Free Language, CFL）”。直接证明一个语言是CFL相对容易，只需为其构造一个上下文无关文法（CFG）或一个下推自动机（PDA）即可。但要证明它不是，就需要一种通用的、具有普适性的反证工具。
2. 类比与回顾：作者首先引导我们回忆之前学过的内容。在第1.4节中，我们学习了用于证明语言不是正则语言的泵引理。这里的“泵”（pumping）可以理解为“注入”或“复制粘贴”，即将字符串的某一部分重复多次。正则语言的泵引理是说，对于一个正则语言，任何足够长的字符串，都可以找到其中一小段，将它重复任意次（或删除），得到的新字符串仍然属于这个正则语言。
3. 引入新工具：本节将介绍一个与正则语言的泵引理类似的工具，专门用于上下文无关语言，我们称之为“上下文无关语言的泵引理”。这个引理同样是基于“泵”的思想。
4. 新工具的核心思想：
   • 适用对象：所有上下文无关语言。
   • 前提条件：语言中存在一个“足够长”的字符串。这个“长”的门槛由一个叫做泵长度（pumping length）的特殊数值 $p$ 决定。任何长度大于等于 $p$ 的字符串都满足泵引理的条件。
   • “泵”的操作：与正则语言的泵引理不同，这次的操作更复杂。正则语言的泵引理将字符串分成三部分 $xyz$，并对中间的 $y$ 进行泵送。而上下文无关语言的泵引理将字符串分成五部分，记为 $s = uvxyz$。
   • 泵送的部分：泵送的对象是第二部分 $v$ 和第四部分 $y$。我们可以将它们同时重复任意次数（包括0次，即删除）。
   • 泵送的结果：经过泵送后得到的新字符串（例如 $uxz$, $uvvxyyz$, $uvvvxyyyz$...）仍然属于原来的上下文无关语言。
5. 复杂性的体现：作者特意指出“这一次，‘泵送’的含义要复杂一些”。这体现在两点：
   • 从三段划分（$xyz$）变成了五段划分（$uvxyz$）。
   • 从泵送一个部分（$y$）变成了泵送两个部分（$v$ 和 $y$）。这种对称性的泵送方式与上下文无关文法的递归结构（特别是嵌套结构）有深刻的联系。

这是泵引理的正式数学描述，非常精炼和严谨。我们来逐句逐条件地拆解它。

定理陈述：

"如果 $A$ 是一个上下文无关语言..."

这是定理的大前提。这个引理只对被确认为CFL的语言 $A$ 生效。我们的应用方式是反证法：先假设一个语言是CFL，然后证明它不满足这个引理的结论，从而推翻假设。

"...那么存在一个数 $p$（泵长度）..."

这说明每个CFL都有一个与之绑定的“魔数” $p$。这个 $p$ 是一个正整数，它的值取决于该语言的具体文法。$p$ 的存在性是定理保证的，但定理本身不告诉我们 $p$ 的具体值是多少。在证明中，我们只需要知道这样一个 $p$ 存在即可。

"...使得对于 $A$ 中任何长度至少为 $p$ 的字符串 $s$..."

这设定了引理生效的范围。它不适用于语言 $A$ 中所有字符串，只适用于那些“足够长”的字符串，即长度 $|s| \ge p$。所有比泵长度 $p$ 短的字符串，引理不对它们做任何承诺。

"...可以将 $s$ 分为五个部分 $s=u v x y z$..."

这是操作的核心。任何满足长度条件的字符串 $s$，都可以被（注意，不是“必须被”）拆分成五段连续的子串。这五段拼接起来必须等于原始的 $s$。

"...满足以下条件："

接下来是三个必须同时被满足的约束条件，这三个条件是泵引理的精髓。

这段话概述了泵引理证明的核心逻辑，它将泵引理的代数性质与上下文无关文法（CFG）的几何结构——分析树（parse tree）——联系起来。

1. 证明的起点：
   • 设 $A$ 是一个CFL。根据定义，必然存在一个CFG $G$ 来生成它。我们的整个证明都将围绕这个文法 $G$ 和它生成的分析树展开。
   • 目标是证明：对于 $A$ 中任何“足够长”的字符串 $s$，我们都能找到一种满足条件的 $uvxyz$ 拆分。
2. 核心关联：长字符串 ↔ 高分析树：
   • 一个字符串 $s$ 是由文法 $G$ 生成的，这意味着存在一个以起始变量为根、以 $s$ 的各个符号为叶子的分析树。
   • 字符串的长度与分析树的“宽度”（叶子节点的数量）直接相关。
   • 文法的规则决定了树的“扇出”（一个节点最多能有多少个孩子）。这个扇出是有限的。
   • 因此，一个非常长的字符串（非常宽的树）必然对应一棵非常高的树。就像一棵树，如果它的树冠要非常宽阔，那么它的树干必然要达到一定的高度。
3. 关键步骤：在长路径上应用鸽巢原理：
   • 高分析树意味着存在一条从根到某个叶子的“长路径”。
   • 这条路径上的节点（除了叶子）都是变量（非终结符）。
   • 文法 $G$ 中的变量数量是有限的，假设有 $|V|$ 个。
   • 如果一条路径上的变量节点数量超过了 $|V|$，根据鸽巢原理（Pigeonhole Principle），必然至少有一个变量在这条路径上出现了不止一次。
   • 鸽巢原理：如果你有 $n+1$ 只鸽子要放进 $n$ 个鸽巢，那么至少有一个鸽巢里有两只或更多的鸽子。在这里，路径上的变量是“鸽子”，文法中的所有变量集合是“鸽巢”。
4. 利用重复变量进行“树的手术”：
   • 我们找到了一个在长路径上重复出现的变量，称之为 $R$。这意味着路径上存在一个较高的 $R$（第一次出现）和一个较低的 $R$（第二次出现）。
   • 较高的 $R$ 作为一个子树的根，生成了 $s$ 的一个子串，我们称之为 $vxy$。
   • 较低的 $R$ 同样作为子树的根，生成了 $vxy$ 内部的一个更小的子串，我们称之为 $x$。
   • 由于这两个子树都源自同一个变量 $R$，它们是“可互换”的。
   • 手术1 (向上泵)：我们可以把较低 $R$ 的子树（生成 $x$）剪掉，然后把较高 $R$ 的子树（生成 $vxy$）复制一份，粘贴到较低 $R$ 的位置。这样，原来的 $x$ 就变成了 $vxy$。整个字符串就从 $uvxyz$ 变成了 $uv(vxy)yz = uvvxyyz = uv^2xy^2z$。这个新生成的树仍然是合法的分析树，所以它生成的字符串一定在语言 $A$ 中。这个过程可以重复任意次，得到 $uv^ixy^iz$。
   • 手术2 (向下泵)：反过来，我们可以把较高 $R$ 的子树（生成 $vxy$）用较低 $R$ 的子树（生成 $x$）来替换。这样，原来的 $vxy$ 就变成了 $x$。整个字符串就从 $uvxyz$ 变成了 $uxz$ ($i=0$ 的情况)。这个新树也是合法的。
5. 五段划分的来源：
   • $u$: 从字符串开头到较高 $R$ 生成部分之前的部分。
   • $v$: 较高 $R$ 生成，但在较低 $R$ 生成部分之前的部分。
   • $x$: 较低 $R$ 生成的部分。
   • $y$: 较高 $R$ 生成，但在较低 $R$ 生成部分之后的部分。
   • $z$: 从较高 $R$ 生成部分结束到字符串末尾的部分。
   • 这五部分的划分是分析树结构在字符串上的直接投影。

这三张图是证明思想的视觉化呈现，展示了“树的手术”过程。

• 第一张图（左上）: 这是“向下泵”（$i=0$）的操作示意图。
• 它展示了一个较大的分析树，树中有一条长路径，路径上有一个较高的变量 $R$ 和一个较低的变量 $R$。
• 较高的 $R$ 根植的子树生成了字符串 $vxy$。
• 较低的 $R$ 根植的子树生成了字符串 $x$。
• 整个字符串被划分为 $uvxyz$。
• “手术”操作是：将较高的 $R$ 及其整个子树，用较低的 $R$ 的子树来替换。
• 结果是，原本由较高 $R$ 生成的 $vxy$ 部分，现在被较低 $R$ 生成的 $x$ 所取代。
• 所以最终生成的字符串是 $uxz$。由于新树仍然是合法的分析树，$uxz$ 必然在语言中。

• 第二张图（左下）: 这是原始的、未经手术的分析树，用于定义 $uvxyz$ 的划分。
• $S$ 是起始变量。
• 树中有一条长路径，上面有两个 $R$。
• $u$: 是较高 $R$ 子树左侧的所有叶子节点组成的字符串。
• $v$: 是较高 $R$ 子树内部，但在较低 $R$ 子树左侧的所有叶子。
• $x$: 是较低 $R$ 子树的所有叶子。
• $y$: 是较高 $R$ 子树内部，但在较低 $R$ 子树右侧的所有叶子。
• $z$: 是较高 $R$ 子树右侧的所有叶子节点组成的字符串。
• 这清晰地展示了 $uvxyz$ 的划分与分析树的结构是如何精确对应的。

• 第三张图（右下）: 这是“向上泵”（$i=2$）的操作示意图。
• 操作与第一张图相反。
• 我们定位到较低的 $R$。
• “手术”操作是：将较低的 $R$ 及其子树（生成 $x$），用较高的 $R$ 的子树（生成 $vxy$）来替换。
• 结果是，原来路径上的 $x$ 部分，被替换成了 $vxy$。
• 所以最终生成的字符串是 $uv(vxy)yz = uvvxyyz = uv^2xy^2z$。
• 这个过程可以重复，如果我们在新生成的 $uv^2xy^2z$ 的分析树中找到最里面那个 $R$，再用生成 $vxy$ 的子树去替换它，就会得到 $uv^3xy^3z$，以此类推。

这部分开始进入证明的严格细节，首先是确定泵长度 $p$ 的值，并建立长字符串和高树之间的数学关系。

1. 确定文法的“扇出”：
   • 设文法为 $G$。$b$ 被定义为 $G$ 中所有规则右侧符号数量的最大值。例如，如果文法有规则 $S \rightarrow aSb$, $A \rightarrow a$, $B \rightarrow cde$，那么这些规则右侧的长度分别是3, 1, 3。所以 $b=3$。
   • $b$ 代表了分析树中一个节点最多能有多少个直接子节点。这决定了树的“分支能力”或“扇出”。
   • 假设 $b \ge 2$ 是为了避免一些退化情况（比如所有规则都是 $A \rightarrow B$ 或 $A \rightarrow a$），这种情况下的树是链状的，需要单独讨论，但核心思想不变。通常可以通过转换文法范式（如乔姆斯基范式，其 $b=2$）来处理。
2. 树高与字符串长度的关系：
   • 高度 (height) $h$ 的树，是指从根到最远叶子的路径长度为 $h$。
   • 如果树高为1，意味着根直接产生叶子，所以最多有 $b^1=b$ 个叶子（字符串长度）。
   • 如果树高为2，第二层的每个节点又最多产生 $b$ 个叶子，所以总叶子数最多是 $b \times b = b^2$。
   • 以此类推，高度为 $h$ 的树，其叶子数量（即生成的字符串长度）最多为 $b^h$。
   • 反向推论（关键）: 这也是一个逆否命题。如果一个字符串的长度 $|s| > b^h$，那么生成它的任何分析树的高度都必须大于 $h$。这是建立“长字符串 → 高树”联系的数学依据。
3. 计算泵长度 $p$：
   • 设 $|V|$ 是文法中变量（非终结符）的总数。这是我们应用鸽巢原理的“巢”的数量。
   • 为了在路径上找到一个重复的变量，我们需要路径上的变量节点数至少为 $|V|+1$。
   • 包含 $|V|+1$ 个变量节点的路径，其总高度（路径长度）至少是 $|V|+1$。
   • 所以，我们需要确保分析树的高度至少是 $|V|+1$。
   • 根据前面树高和字符串长度的关系，要保证树高至少为 $|V|+1$，我们需要的字符串长度至少要大于 $b^{|V|}$。
   • 因此，我们选择一个足够大的数作为泵长度 $p$。证明中选择 $p = b^{|V|+1}$。
   • 为什么是这个值？因为当字符串 $s$ 的长度 $|s| \ge p = b^{|V|+1}` 时，我们来计算它的树高 `$h_s$`。根据反向推论，`$h_s 必须大于 $|V|+1$ 吗？不完全是。当 $|s| \ge b^{h}+1$ 时，树高至少为 $h+1$。
   • 这里作者用了一个不等式：$b^{|V|+1} \geq b^{|V|}+1$（这个不等式在 $b \ge 2, |V| \ge 1$ 时成立）。
   • 所以，如果 $|s| \ge p = b^{|V|+1}$，那么 $|s| \ge b^{|V|}+1$。
   • 根据 $h= |V|` 的情况，如果字符串长度至少为 `$b^{|V|}+1$`，其树高必须至少为 `$|V|+1$。
   • 结论：当 $|s| \ge p = b^{|V|+1}$ 时，生成 $s$ 的任何分析树的高度都至少为 $|V|+1$。

这部分开始在已确认足够高的分析树上，精确地找出用于“手术”的重复变量 $R$。

1. 选择一个“最小”的分析树：
   • 一个字符串 $s$ 可能由一个歧义文法生成，从而有多个不同的分析树。
   • 为了确保后续证明的严谨性（特别是为了满足条件2 $|vy|>0$），这里做了一个巧妙的选择：如果 $s$ 有多个分析树，我们选择那个节点总数最少的树，记为 $\tau$。这个选择将在后面发挥关键作用。
2. 定位长路径和重复变量：
   • 我们已经证明，对于长度 $|s| \ge p$ 的字符串，其任何分析树 $\tau$ 的高度都至少是 $|V|+1$。
   • 树的高度由最长路径决定，所以 $\tau$ 中存在一条从根到某个叶子的路径，其长度（边的数量）至少为 $|V|+1$。
   • 一条长度为 $h$ 的路径上有 $h+1$ 个节点。所以这条最长路径上至少有 $|V|+2$ 个节点。
   • 这些节点中，终点（叶子）是一个终结符，其余的 $|V|+1$ 个或更多节点都是变量。
   • 现在我们有了一条路径，上面至少有 $|V|+1$ 个变量。根据鸽巢原理（$|V|+1$ 只鸽子，$|V|$ 个巢），其中必有变量是重复的。
3. 精确选择重复变量 $R$：
   • 路径上可能有多个变量重复多次。例如，路径可能是 S-A-B-C-A-D-B-E，其中 A 和 B 都重复了。
   • 为了满足后面的条件3 ($|vxy| \le p$)，我们需要对 $R$ 的选择做一个限制。
   • 证明中的选择是：考察这条最长路径上，从叶子节点往上数的、最底部的 $|V|+1$ 个变量。
   • 在这 $|V|+1$ 个变量中，必然存在重复（再次应用鸽巢原理）。我们选择这个重复的变量作为我们的 $R$。
   • 这个选择意味着，我们找到的两个重复的 $R$（一个较高，一个较低）都位于离叶子很近的地方。这保证了由较高的 $R$ 生成的子树不会太高，从而它生成的字符串 $vxy$ 也不会太长。

这部分基于已找到的重复变量 $R$，正式进行“树的手术”，并证明这满足了泵引理的条件1。

1. 划分字符串 $uvxyz$：
   • 如之前图示所解释，字符串 $s$ 的五段划分是分析树在叶子层面的直接投影。
   • 较高的 $R$ (记为 $R_{upper}$) 生成的子串是 $vxy$。
   • 较低的 $R$ (记为 $R_{lower}$) 生成的子串是 $x$。
   • $u, v, y, z$ 是围绕着 $x$ 和 $vxy$ 的其余部分。
2. 进行“树的手术”并验证条件1：
   • 向下泵 ($i=0$): 在分析树 $\tau$ 中，将 $R_{upper}$ 子树替换为 $R_{lower}$ 子树。因为 $R_{upper}` 和 `$R_{lower} 都是同一个变量 $R$，所以这种替换是语法允许的。新生成的分析树是合法的。它生成的字符串就是 $uxz$。因此，$uxz \in A$。
   • 向上泵 ($i > 1$): 在分析树 $\tau$ 中，找到 $R_{lower}$ 子树，将其替换为 $R_{upper}$ 子树。新树也是合法的。它生成的字符串是 $uv(vxy)yz = uv^2xy^2z$。因此，$uv^2xy^2z \in A$。这个过程可以迭代进行，在新的、更大的树中再次找到最里面的 $R`，再次替换，从而生成 `$uv^ixy^iz$` 对于所有的 `$i>1$。
   • 综上所述，对于任何 $i \ge 0$，字符串 $uv^ixy^iz$ 都有一个合法的分析树，因此它一定属于语言 $A$。这就严格证明了条件1。

这里解释了为什么条件2 ($|vy|>0$)必须成立。证明用到了之前埋下的一个伏笔：我们选择了节点数最少的分析树 $\tau$。

1. 假设条件2不成立：我们用反证法。假设条件2不成立，即 $|vy|=0$。这意味着 $v = \epsilon$ 并且 $y = \epsilon$。
2. 分析后果：
   • 如果 $v=\epsilon$ 且 $y=\epsilon$，那么 $vxy=x$。
   • 我们知道 $R_{upper}$ 生成 $vxy$，$R_{lower}$ 生成 $x$。
   • 这意味着 $R_{upper}$ 和 $R_{lower}$ 生成了完全相同的字符串 $x$。
   • 但是，$R_{upper}$ 在路径上比 $R_{lower}$ 更高，所以从 $R_{upper}` 到它生成叶子 `$x$` 的推导路径，必然比从 `$R_{lower} 到它生成叶子 $x$ 的路径要长。这意味着 $R_{upper}` 的子树至少比 `$R_{lower} 的子树多一个推导层级（即 $R_{upper} \rightarrow ... \rightarrow R_{lower}$ 这一步）。
   • 因此，$R_{upper}$ 子树的节点数严格大于 $R_{lower}$ 子树的节点数。
3. 构造更小的树：
   • 现在，我们对原始的、节点数最少的分析树 $\tau$ 进行“向下泵”手术：用 $R_{lower}$ 子树替换 $R_{upper}$ 子树。
   • 手术后的新树，其生成的字符串是 $uxz$。
   • 但因为我们假设了 $v=\epsilon, y=\epsilon$，所以 $uxz = u\epsilon x \epsilon z = uvxyz = s$。
   • 这意味着，手术后的新树生成的字符串仍然是 $s$！
   • 但是，由于 $R_{upper}$ 子树的节点数大于 $R_{lower}$ 子树，这次替换使得新树的总结点数严格小于 $\tau$ 的节点数。
4. 导出矛盾：
   • 我们找到了一个生成同样字符串 $s$ 的、但节点数更少的分析树。
   • 这与我们最初选择 $\tau$ 作为“节点数量最少的分析树”相矛盾。
   • 因此，我们的初始假设（$|vy|=0$）必然是错误的。
   • 结论：$|vy| 必须大于0。条件2得证。

最后，这里解释了为什么条件3 ($|vxy| \le p$)成立。这又用到了之前埋下的另一个伏笔：我们对重复变量 $R$ 的精确选择方法。

1. 回顾 $R$ 的选择：我们不是在整条长路径上随便找一个重复变量，而是先定位到最长路径，然后考察这条路径最底部的 $|V|+1$ 个变量，并在这里面找到重复的 $R$。
2. $R_{upper} 子树的高度：
   • $R_{upper}$ 是这两个重复 $R$ 中较高的一个。
   • 由于这两个 $R$ 都位于离叶子很近的、长度为 $|V|+1$ 的路径段上，所以从 $R_{upper}$ 节点出发，沿着这条最长路径走到叶子，经过的节点数不会超过 $|V|+1$。
   • 这意味着，以 $R_{upper}` 为根的子树，其高度至多为 `$|V|+1$`。（这里有一个微妙之处，如果 `$R_{upper} 生成的子树内部有另一条更长的路径怎么办？证明选择最长路径 $\tau$ 上的重复变量，可以规避这个问题。严格的证明会更复杂，但这是基本思想。）
3. 子树高度与生成字符串长度的关系：
   • 我们已经建立了关系：一个高度为 $h$ 的树，最多能生成长度为 $b^h$ 的字符串。
   • 现在我们知道 $R_{upper}` 子树的高度至多是 `$|V|+1$。
   • 因此，它生成的字符串 $vxy$ 的长度 $|vxy|$ 至多是 $b^{|V|+1}$。
4. 与 $p$ 的关系：
   • 我们在一开始就定义了泵长度 $p = b^{|V|+1}$。
   • 所以，我们得到了 $|vxy| \le b^{|V|+1} = p$。
   • 条件3得证。

这段话是一个提醒和引导，告诉读者使用这个新工具的策略和之前学习的正则泵引理是相通的。

使用泵引理进行反证法的通用“游戏脚本”：

1. 你的回合（宣称）: 宣称你要证明语言 $L$ 不是CFL。
2. 对手的回合（泵引理）: 对手（泵引理）说：“好，如果 $L$ 是CFL，那么它一定有一个泵长度 $p$。这个 $p$ 是多少我不能告诉你，但它存在。”
3. 你的回合（选择字符串）: 这是最关键的一步。你必须选择一个特殊的、足够“刁难”的字符串 $s$。这个 $s$ 必须：
   • 在语言 $L$ 中。
   • 其长度与 $p$ 相关，且长度 $|s| \ge p$。通常我们会选择像 $a^p b^p c^p$ 或 $0^p 1^p 0^p 1^p$ 这样的字符串，它们的结构与语言的核心特性紧密相关。
4. 对手的回合（拆分字符串）: 对手说：“根据引理，你选的这个 $s$，我保证存在一种拆分方式 $s=uvxyz$，它同时满足三个条件：
   • 1. $uv^ixy^iz \in L$
   • 2. $|vy|>0$
   • 3. $|vxy| \le p$
5. 你的回合（将军！）: 你的任务是证明对手在撒谎。你必须证明，无论对手如何拆分 $s$，只要他遵守规则2和3，规则1就必然被打破。你需要考虑所有可能的拆分情况，并一一说明它们如何导致矛盾。
   • 通常的策略是利用条件3 ($|vxy| \le p$) 来缩小 $v,y$ 的可能位置。
   • 然后分类讨论 $v,y$ 中包含哪些字符。
   • 最后，选择一个合适的 $i$ (通常是 $i=0$ 或 $i=2$)，证明泵送后的字符串 $uv^ixy^iz$ 不在语言 $L$ 中，从而产生矛盾。
6. 宣布胜利: 因为你找到了一个矛盾，所以最初的假设——“$L$ 是CFL”——是错误的。因此，$L$ 不是CFL。

这个过程就像一场逻辑对战，你的目标是把泵引理的承诺逼入死角，让它无法自圆其说。

这是一个经典的、使用泵引理证明非CFL的范例。

1. 第一步：假设与选择
   • 假设: 假设语言 $B = \{a^n b^n c^n \mid n \ge 0\}$ 是一个CFL。
   • 获取泵长度: 根据假设，泵引理适用，因此存在一个泵长度 $p$。
   • 选择测试字符串: 我们选择 $s = a^p b^p c^p$。
   • 这个字符串在 $B$ 中（取 $n=p$）。
   • 它的长度是 $3p$，显然 $3p \ge p$（因为 $p \ge 1$）。
   • 这个字符串完美地体现了语言 $B$ 的核心约束：三组符号数量必须完全相等。
2. 第二步：应用引理并准备反驳
   • 泵引理断言：$s = a^p b^p c^p$ 可以被拆分为 $uvxyz$，满足那三个条件。
   • 我们的任务是证明：不可能存在这样的拆分。我们将通过分析所有可能的拆分方式来证明这一点。
3. 第三步：分类讨论所有可能的拆分
   • 这里的分类是基于 $v$ 和 $y$ 所包含的字符种类。在开始分类前，我们先利用条件3 ($|vxy| \le p$) 来大大简化问题。
   • 关键洞察: 字符串 $s=a^p b^p c^p$。子串 $vxy$ 的长度不超过 $p$。这意味着 $vxy$ 不可能同时包含 'a' 和 'c'。因为从最后一个 'a' 到第一个 'c' 的距离是 $p+1$ ($b^p$ 加上第一个'c')。所以 $vxy$ 要么只包含 'a'，要么只包含 'b'，要么只包含 'c'，要么包含 'a' 和 'b' 的混合，要么包含 'b' 和 'c' 的混合。它绝不可能横跨三界。
   • 现在我们来看原文的分类：

• 情况1：$v$ 和 $y$ 都只包含一种字母符号类型。
• 这意味着 $v$ 是 $a...a$，或者 $b...b$，或者 $c...c$ (或者空串)。$y$ 也类似。
• 由于 $|vxy| \le p$，$vxy$ 不可能同时有a和c。所以$v$和$y$中的字符，要么全是a，要么全是b，要么全是c，或者$v$是a串，$y$是b串等。
• 根据条件2 ($|vy|>0$), $v$ 和 $y$ 至少有一个非空。
• 泵送 $uv^2xy^2z$ (向上泵, $i=2$):
• 这个操作会增加 $s$ 中某些符号的数量。
• 由于 $v$ 和 $y$ 不可能同时包含 'a', 'b', 'c' 三种符号（因为 $|vxy| \le p$），所以泵送操作必然会打破三者数量的平衡。
• 例如，如果 $v=a^k, y=b^j$ ($k+j > 0$)，新字符串中 'a' 的数量是 $p+k$, 'b' 的数量是 $p+j$, 'c' 的数量是 $p$。由于 $k+j>0$, $p+k, p+j, p$ 这三个数不可能相等。
• 如果 $v$ 和 $y$ 都只包含 'b'，那么新字符串中 'a' 和 'c' 的数量是 $p$，但 'b' 的数量大于 $p$。
• 在任何子情况下，泵送后的字符串中 'a', 'b', 'c' 的数量不再相等。
• 因此，$uv^2xy^2z \notin B$。这与泵引理的条件1矛盾。

• 情况2：$v$ 或 $y$ 包含多于一种符号类型。
• 由于 $|vxy| \le p$，这意味着 $v$ (或 $y$) 只能是 'a...ab...b' 形式或 'b...bc...c' 形式。它不可能是 'a...c' 形式。
• 假设 $v = a^k b^j$ ($k,j \ge 1$)。
• 那么字符串 $s$ 的一部分看起来像 ...a(a^k b^j)b...。
• 当我们向上泵送（$i=2$）时，会得到 $uv^2xy^2z$，这部分会变成 ...a(a^k b^j)(a^k b^j)b...。
• 在结果字符串中，出现了一个 'b' 在一个 'a' 之前的情况 (...bja^k...)。
• 这破坏了 $a...ab...bc...c$ 的顺序。
• 因此，$uv^2xy^2z \notin B$。这也与泵引理的条件1矛盾。

1. 第四步：得出结论
   • 我们已经考虑了所有可能的拆分情况（基于 $v, y$ 的内容），并且证明了在每种情况下都会导致矛盾。
   • 因此，不存在满足泵引理条件的拆分。
   • 这与泵引理的断言（“如果 $B$ 是CFL，则必须存在这样的拆分”）相矛盾。
   • 所以，我们的初始假设（“$B$ 是CFL”）是错误的。
   • 结论：$B = \{a^n b^n c^n \mid n \ge 0\}$ 不是一个上下文无关语言。

这个例子比前一个更微妙，因为它处理的是不等关系 $i \le j \le k$ 而不是相等关系 $n=n=n$。

1. 第一步：假设与选择
   • 假设: 语言 $C = \{a^i b^j c^k \mid 0 \le i \le j \le k\}$ 是 CFL。
   • 获取泵长度: 存在泵长度 $p$。
   • 选择测试字符串: 再次选择 $s = a^p b^p c^p$。
   • 这个字符串在 $C$ 中，因为当 $i=j=k=p$ 时，$p \le p \le p$ 成立。
   • 长度为 $3p \ge p$。
   • 这个字符串处于约束条件的“临界”状态，稍微改变数字就很容易破坏不等关系，因此是个很好的测试样本。
2. 第二步：应用引理并准备反驳
   • 引理说 $s = a^p b^p c^p$ 可被拆分为 $uvxyz$ 并满足三条件。
   • 我们将证明这是不可能的。
3. 第三步：分类讨论
   • 同样，我们利用 $|vxy| \le p$。这意味着 $vxy$ 不可能同时包含 'a' 和 'c'。
   • 情况1：$v$ 和 $y$ 都只包含一种字母符号类型（即不跨界）。
   • 作者指出，不能像上一个例子那样简单地说“数量不相等了”。因为语言 $C$ 允许数量不相等。
   • 这里的关键洞察是：由于 $|vxy| \le p$，$vxy$ 不可能同时包含 'a' 和 'c'。因此，在 $v$ 和 $y$ 中，至少有一种符号（'a', 'b' 或 'c') 没有出现。
   • 我们根据“哪个符号没有被泵送”来进一步细分。

• 子情况 1.a: $v,y$ 中不包含 'a'。
• 这意味着 $v,y$ 只由 'b' 和/或 'c' 组成。
• 由于 $|vy|>0$，所以泵送会减少 'b' 的数量，或减少 'c' 的数量，或同时减少。
• 'a' 的数量保持不变，仍为 $p$。
• 我们向下泵 ($i=0$)，得到字符串 $s' = uxz$。
• $s'` 中 a 的数量是 `$N_a' = p$.
• $s'` 中 b 的数量是 `$N_b' < p$` 或 c 的数量是 `$N_c' < p$ (或两者都小于)。
• 这导致 $N_a' > N_b'$ 或 $N_a' > N_c'$(因为`$N_b' \le N_c'` 或 `$N_c' \le N_b'$ 的关系可能保持)。
• 但是 $s'$ 要属于 $C$，必须满足 $N_a' \le N_b' \le N_c'$。
• 我们已经有 $N_a' = p$ 和 $N_b' < p$ 或 $N_c' < p$。如果 $N_b' < p$，则 $N_a' > N_b'$，这违反了 $i \le j$。如果只有 $N_c'` 减少，则 `$N_b' = p$`, `$N_c' < p$`，这违反了 `$j \le k$`。
• 所以 $s' \notin C$。矛盾。

• 子情况 1.b: $v,y$ 中不包含 'b'。
• 这意味着 $v,y$ 只由 'a' 和/或 'c' 组成。$|vy|>0$。
• **如果 $v` 或 `$y$` 中有 'a'**: 我们**向上泵** (`$i=2$`)，得到 `$s' = uv^2xy^2z$。
• $N_a' > p$, $N_b' = p$, $N_c' \ge p$。
• 由于 $N_a' > p$ 而 $N_b' = p$，这违反了 $i \le j$ 的约束。
• 所以 $s' \notin C$。矛盾。
• **如果 $v` 或 `$y$` 中只有 'c'**: 我们**向下泵** (`$i=0$`)，得到 `$s' = uxz$。
• $N_a' = p$, $N_b' = p$, $N_c' < p$。
• 由于 $N_b' = p$ 而 $N_c' < p$，这违反了 $j \le k$ 的约束。
• 所以 $s' \notin C$。矛盾。
• 两种子情况都导致矛盾。

• 子情况 1.c: $v,y$ 中不包含 'c'。
• 这意味着 $v,y$ 只由 'a' 和/或 'b' 组成。$|vy|>0$。
• 我们向上泵 ($i=2$)，得到 $s' = uv^2xy^2z$。
• $N_a' \ge p$, $N_b' \ge p$, $N_c' = p$。
• 由于 $|vy|>0$，$v,y$ 中至少有一个非空，所以 $N_a' > p$ 或 $N_b' > p$ (或都成立)。
• 如果 $N_b' > p$，那么 $N_b' > N_c' = p$，违反 $j \le k$。
• 如果 $N_a' > p$ 且 $N_b'=p$，那么 $N_a' > N_b'`，违反 `$i \le j$。
• 唯一可能不直接矛盾的情况是 $v$ 只含a，$y$ 只含b，$uv^2xy^2z$ 变成了 $a^{p+|v|} b^{p+|y|} c^p$。但只要 $|y|>0$，就会有 $p+|y| > p$，即 $j>k$，矛盾。如果 $|y|=0$，则 $|v|>0$，$a^{p+|v|} b^p c^p$，$i>j$，矛盾。
• 总之，只要增加了 a 或 b 的数量，而 c 的数量不变，$j \le k$ 或 $i \le j$ 必被破坏。
• 所以 $s' \notin C$。矛盾。

• 情况2：$v$ 或 $y$ 包含多于一种符号类型。
• 这和上一个例子完全一样。由于 $|vxy| \le p$，这种跨界只可能发生在 ab 之间或 bc 之间。
• 向上泵送会导致字符顺序错乱，例如 ...ba... 或 ...cb...。
• 所以 $uv^2xy^2z \notin C$。矛盾。

1. 第四步：结论
   • 所有情况都导向矛盾，因此 $s = a^p b^p c^p$ 无法被泵送。
   • 这与泵引理矛盾，所以假设错误。
   • $C 不是 CFL。

这个例子展示了如何为具有“复制”结构的语言选择合适的测试字符串，并突出了条件3 ($|vxy| \le p$) 的决定性作用。

1. 第一步：假设与第一次尝试
   • 假设: 语言 $D = \{ww \mid w \in \{0,1\}^*\}$ 是 CFL。
   • 获取泵长度: 存在泵长度 $p$。
   • 第一次选择字符串: 作者首先尝试了一个看似合理的字符串 $s = 0^p10^p1$。这里 $w=0^p1$。
   • 这个字符串在 $D$ 中，长度 $2p+2 \ge p$。
   • 失败原因: 作者指出这个字符串可以被泵送。我们来分析一下他给出的拆分：
   • $s = (0^{p-1})(0)(1)(0)(0^{p-1}1)$
   • $u = 0^{p-1}$
   • $v = 0$
   • $x = 1$
   • $y = 0$
   • $z = 0^{p-1}1$
   • 让我们检查条件：
2. 泵送: $uv^ixy^iz = 0^{p-1}(0)^i 1 (0)^i 0^{p-1}1 = 0^{p-1+i}10^{p-1+i}1$。这个新字符串的形式是 $w'w'`，其中 `$w' = 0^{p-1+i}1$`。所以它总是在语言 `$D$ 中。条件1满足。
3. 非空: $|vy|=|00|=2 > 0$。条件2满足。
4. 长度限制: $|vxy|=|010|=3$。只要 $p \ge 3$，这个条件就满足。
   • 结论：因为我们找到了一个成功的泵送方案，所以字符串 $0^p10^p1$ 不能用来证明 $D$ 非CFL。选择测试字符串是一门艺术。
5. 第二步：第二次尝试，选择更好的字符串
   • 选择: 作者选择了 $s = 0^p 1^p 0^p 1^p$。
   • 这里 $w = 0^p 1^p$，所以 $s=ww$ 在 $D$ 中。
   • 长度是 $4p \ge p$。
   • 这个字符串的结构更复杂，前后两半 $w$ 内部都有两种字符，这使得泵送更难保持 $w'w' 的形式。
6. 第三步：利用条件3进行反驳
   • 泵引理说 $s = 0^p 1^p 0^p 1^p$ 可以被拆分。我们的目标是证明它不行。
   • $s$ 的中点在第一个 $1^p$ 和第二个 $0^p$ 之间。前半部分是 $0^p1^p$，后半部分是 $0^p1^p$。
   • 核心论证: 利用 $|vxy| \le p$。这个窗口太小了。
   • $s = \underbrace{0...0}_{p} \underbrace{1...1}_{p} | \underbrace{0...0}_{p} \underbrace{1...1}_{p}$ ( | 是中点)
   • $vxy$ 是一个长度不超过 $p$ 的子串。

• 情况1：$vxy$ 完全位于 $s$ 的前半部分 ($0^p1^p$)。
• 这意味着泵送操作只修改前半部分。
• 后半部分 $0^p1^p$ 保持不变。
• 向上泵 ($i=2$) 或向下泵 ($i=0$) 会改变前半部分的字符串（因为 $|vy|>0$）。
• 泵送后的字符串 $s'` 的前半部分不再等于 `$0^p1^p$。
• 因此，$s'` 不再是 `$w'w' 的形式（因为后半部分没变，而前半部分变了）。
• $s' \notin D$。矛盾。
• 原文中说“会将一个 '1' 移动到后半部分的第一个位置”，这是一种更具体的描述，但有点令人困惑。核心思想是前后两半不再匹配。

• 情况2：$vxy$ 完全位于 $s$ 的后半部分 ($0^p1^p$)。
• 同理，泵送只修改后半部分，前半部分不变。
• 泵送后的字符串 $s' 的两半不再匹配。
• $s' \notin D$。矛盾。

• 情况3：$vxy$ 跨越了 $s$ 的中点。
• $s = 0^p \underbrace{1...1}_{p} | \underbrace{0...0}_{p} 1^p$
• 由于 $|vxy| \le p$，这个窗口的长度是 $p$。它最多能覆盖中点左侧的 $1^p$ 的一部分和中点右侧的 $0^p$ 的一部分。
• 具体来说，$vxy$ 必定是 $1^k 0^j$ 的形式，其中 $k+j \le p$。
• 这意味着 $v$ 和 $y$ 只能由 '1' 和/或 '0' 组成，且它们都位于 $s$ 的中间区域。
• 例如，一个可能的拆分是：
• $u = 0^p 1^{p-a}
• $v = 1^a$
• $x = 1^b 0^c$
• $y = 0^d$
• $z = 0^{p-c-d} 1^p$
• 其中 $|vxy| = a+b+c+d \le p$。
• 我们来考虑泵送后的结果。原文建议向下泵 ($i=0$)，得到 $s' = uxz$:
• $s' = (0^p 1^{p-a}) (1^b 0^c) (0^{p-c-d} 1^p) = 0^p 1^{p-a+b} 0^{p-d} 1^p$。
• 因为 $|vy| = a+d > 0$，所以 $a`和`$d$不全为0。
• 新的前半部分是 $w'_{first} = 0^p 1^{p-a+b}$。
• 新的后半部分是 $w'_{second} = 0^{p-d} 1^p$。
• 为了让 $s'` 仍在 `$D$` 中，必须有 `$w'_{first} = w'_{second}$。
• 即 $0^p 1^{p-a+b} = 0^{p-d} 1^p$。
• 这要求 $p = p-d$ (0的数量相等) 且 $p-a+b = p$ (1的数量相等)。
• $p = p-d \Rightarrow d=0$。
• $p-a+b = p \Rightarrow b=a$。
• 但是，我们还知道 $v, x, y$ 的构成。$v=1^a, x=1^b0^c, y=0^d$。
• 如果 $d=0$，那么 $a>0$ (因为 $a+d>0$)。
• 如果 $b=a$，那么 $v=1^a, x=1^a0^c$。
• $|vxy| = a + (a+c) + 0 = 2a+c \le p$。
• 这个推理链并没有直接导出矛盾。原文的论证更简洁。
• 让我们回到原文的简洁论证:
• 当 $vxy$ 跨越中点时，泵送 $s$ 到 $uxz$ ($i=0$)。
• $s = 0^p 1^p 0^p 1^p$。
• $uxz$ 是通过从 $s$ 中删除 $v$ 和 $y$ 得到的。
• $v$ 和 $y$ 都位于 $s$ 的中间部分（由一些1和一些0组成）。
• 所以，$uxz$ 的形式是 $0^p 1^i 0^j 1^p$，其中 $i \le p, j \le p$。
• 因为 $|vy| > 0$，所以我们从原来的 $1^p 0^p$ 中至少删除一个字符。这意味着 $i` 和 `$j$` 不能同时等于 `$p$。
• 那么，$uxz = 0^p 1^i 0^j 1^p$ 这个字符串的总长度是 $p+i+j+p < 4p$。
• 它的前半部分长度是 $(2p+i+j)/2$，后半部分也是。
• 我们能说这个字符串不是 $w'w' 形式吗？
• 假设 $uxz = w'w'`。那么 `$w' 必须以 $0^p$ 开头吗？不一定。$w'` 可能是 `$0^k$。
• 这里有一个更强的论证：任何 $ww$ 形式的字符串，其长度必须是偶数。$|s|=4p$ 是偶数。$|uxz| = 4p - |vy|`。如果 `$|vy|$` 是奇数，`$|uxz|$` 就是奇数，不可能写成 `$w'w'。那么 $|vy|$ 可能是奇数吗？是的，比如 $v=1, y=\epsilon$。
• 如果 $|vy|$ 是偶数呢？$uxz$ 长度是偶数。例如，$v=1, y=0$。$uxz = 0^p 1^{p-1} 0^{p-1} 1^p$。这个字符串的前半部分是 $0^p 1^{p-1}$，后半部分是 $0^{p-1} 1^p$。它们显然不相等。
• 所以，无论如何，泵送后的字符串都不再具有 $w'w' 的形式。
• $uxz \notin D$。矛盾。

1. 第四步：结论
   • 所有三种 $vxy$ 的位置（前半、后半、跨中点）都导致矛盾。
   • 因此 $s = 0^p 1^p 0^p 1^p$ 不能被泵送。
   • 假设错误，$D 不是 CFL。