1. Handout 4B: Solutions to Practice Problems

这段话首先定义了一个语言 $L_1$。这个语言由一串 0 后面跟着一串 1 组成。它的核心约束条件是：0 的数量（表示为 $n$）不等于 1 的数量（表示为 $m$）。

然后，它提出了一个论点：语言 $L_1$ 是一个非正则语言。正则语言是指可以用有限自动机（DFA 或 NFA）识别的语言。非正则语言则不能。直观地想，有限自动机的“记忆”是有限的，它无法记住一个任意大的数字。而要判断 $n$ 是否等于 $m$，机器需要精确地“计数”0 的数量，然后用这个计数值去比对 1 的数量。当 $n$ 和 $m$ 可以是任意大的数时，这超出了有限自动机的能力范围。

最后，这段话预告了将使用三种不同的数学工具来证明 $L_1$ 的非正则性：

1. 泵引理（Pumping Lemma）：一个用于证明语言非正则的经典反证法工具。
2. 正则语言的封闭性（Closure Properties）：利用正则语言在某些运算（如交集、并集、补集）下是封闭的这一特性来构造矛盾。
3. Myhill-Nerode 定理：一个更强大、更根本的工具，通过考察语言的等价类数量来判断其是否正则。

它还特别指出，对于 $L_1$ 这个特定的例子，泵引理的证明过程最为复杂，而另外两种方法则相对直接和简单。

这部分内容是一个教学性的演示，它展示了一个在使用泵引理时常见的错误。泵引理是一个反证法工具，其逻辑是：

1. 假设语言 $L$ 是正则的。
2. 那么，存在一个泵长度 $p$。
3. 我们（证明者）选择一个足够长的字符串 $w \in L$ (长度 $|w| \ge p$）。
4. 对手（泵引理）将 $w$ 分割成 $xyz$，并遵循三个规则：
   • $|xy| \le p$ (分割点在前部)
   • $|y| > 0$ (中间部分非空)
   • 对于所有 $i \ge 0$，$xy^iz \in L$ (可以任意“泵送”$y$)
5. 我们的目标是，通过选择一个合适的 $i$（通常不是 1），使得泵送后的字符串 $xy^iz$ 不在语言 $L$ 中，从而产生矛盾。如果能做到，就说明最初的假设是错的，$L$ 非正则。

这段文字的精髓在于，它选择了一个看似合理的字符串 $w=0^p 1^{p+1}$，并展示了为什么这个选择是失败的。

• 选择的字符串: $w=0^p 1^{p+1}$。这个字符串在 $L_1$ 中，因为 0 的数量 ($p$) 不等于 1 的数量 ($p+1$)。它的长度是 $2p+1$，也满足 $\ge p$ 的要求。
• 对手的分割: 根据规则 $|xy| \le p$ 和 $w$ 的结构，xy 部分必须完全由 0 组成。又因为 $|y|>0$，$y$ 必须是至少一个 0，即 $y=0^k$ for $1 \le k \le p$。
• 泵送: 泵送后的字符串是 $0^{p+(i-1)k}1^{p+1}$。
• 寻找矛盾: 我们的目标是找到一个 $i \ge 0$ 使得泵送后的字符串不在 $L_1$ 中。一个字符串不在 $L_1$ 中只有一种可能（在格式正确的前提下）：0 的数量等于 1 的数量。所以，我们需要找到 $i$ 使得 $p+(i-1)k = p+1$。
• 失败点: 这个方程化简为 $(i-1)k = 1$。因为 $i$ 和 $k$ 都必须是正整数，这个方程唯一的整数解是 $i-1=1$ 且 $k=1$，即 $i=2, k=1$。
• 如果对手恰好选择 $k=1$ (即 $y='0'$)，那么我们选择 $i=2$，泵出的字符串是 $0^{p+1}1^{p+1}$，0 和 1 的数量相等，不在 $L_1$ 中，我们就成功制造了矛盾。
• 但是，我们无法控制对手！对手可以选择任何满足 $1 \le k \le p$ 的 $k$。如果对手选择 $k=2$ 呢？方程就变成了 $(i-1)2 = 1$，这没有整数解 $i$。这意味着，如果 $k=2$，无论我们怎么泵送（选择任何 $i$），0 的数量将是 $p+2(i-1)$，这个数永远不可能等于 $p+1$。泵送后的字符串将永远在 $L_1$ 中，我们无法制造矛盾。

因为我们必须找到一个对所有可能的分割都有效的矛盾，而对于 $w=0^p 1^{p+1}$，我们至少有一种分割（例如 $k=2$）无法导出矛盾，所以这次证明尝试失败了。

这是泵引理证明的正确版本。这里的关键在于选择了一个更巧妙的字符串 $w$。

1. 选择字符串: 我们选择 $w = 0^p 1^{p+p!}$。
   • $p!$ (p 的阶乘) 定义为 $p \times (p-1) \times \dots \times 1$。
   • 这个字符串在 $L_1$ 中，因为 $p$ 永远不等于 $p+p!$ (由于 $p! \ge 1$ for $p \ge 1$)。
   • 它的长度是 $2p+p!$，对于 $p \ge 1$，这个长度大于 $p$。
2. 对手的分割: 同样，根据 $|xy| \le p$ 和 $|y|>0$，$y$ 必须是 $0^k$ 的形式，其中 $k$ 是一个整数，满足 $1 \le k \le p$。
3. 寻找矛盾的目标: 我们要泵送 $y$，使得泵送后的字符串 $w'$ 中 0 的数量等于 1 的数量。
   • $w$ 中 0 的数量是 $p$。
   • $w$ 中 1 的数量是 $p+p!$。
   • 泵送 $i$ 次后， $y=0^k$ 被复制了 $i$ 次，总共增加了 $(i-1)k$ 个 0。
   • $w'$ 中 0 的数量是 $p + (i-1)k$。
   • 我们的目标是令：$p + (i-1)k = p+p!$。
4. 解决矛盾: 上述方程简化为 $(i-1)k = p!$。
   • 我们需要找到一个整数 $i \ge 0$ 来满足这个方程。
   • 解出 $i$：$i-1 = \frac{p!}{k}$，所以 $i = \frac{p!}{k} + 1$。
5. 证明可行性:
   • 我们不知道 $k$ 是多少，但我们知道 $1 \le k \le p$。
   • 一个关键的数学事实是：$p!$ (p的阶乘) 定义为 $p \times (p-1) \times \dots \times k \times \dots \times 1$。因此，$p!$ 必然能被 $1$ 到 $p$ 之间的任何整数 $k$ 整除。
   • 所以，$\frac{p!}{k}$ 必然是一个整数。
   • 因此，$i = \frac{p!}{k} + 1$ 也必然是一个整数。
   • 同时，因为 $k \ge 1$，$p! \ge 1$，所以 $i \ge 2$，满足 $i \ge 0$ 的条件。
6. 得出结论: 我们已经证明，无论对手选择哪个 $k$ ($1 \le k \le p$)，我们总能找到一个对应的整数 $i = \frac{p!}{k} + 1$。当使用这个 $i$ 进行泵送时，得到的字符串 $w'$ 拥有 $p+p!$ 个 0 和 $p+p!$ 个 1。这个 $w'$ 因为 0 和 1 数量相等而不属于 $L_1$。

这与泵引理的第三条规则（所有 $xy^iz$ 都必须在 $L_1$ 中）产生了矛盾。

因此，我们最初的假设“$L_1$ 是正则的”是错误的。结论：$L_1$ 非正则。

这个证明方法比泵引理更简洁，它利用了正则语言的封闭性质。封闭性意味着，对正则语言进行某些运算（如并集、交集、补集、连接、星号闭包等），其结果仍然是正则语言。

该证明的逻辑是一个经典的反证法：

1. 假设 $L_1$ 是正则的：这是我们要推翻的起点。
2. 应用封闭性：
   • 正则语言对补集运算是封闭的。如果 $L_1$ 正则，那么它的补集 $L_1^c$ 也必须是正则的。
   • $L_1$ 的补集是什么？$L_1^c$ 包含了所有不在 $L_1$ 中的字符串。这包括两种情况：
3. 引入已知语言：
   • $L_{eq} = \{0^n 1^n \mid n \ge 0\}$: 这是我们课堂上已经证明过的是非正则的语言。
   • $L_{all} = \{0^m 1^n \mid m, n \ge 0\}$: 这是一个正则语言。它的正则表达式是 01。
4. 构造关系: 证明的核心是展示如何通过已知的正则操作从我们假设的正则语言构造出已知的非正则语言。
   • 观察 $L_1^c \cap L_{all}$：
   • $L_1^c$ 包含所有 $m=n$ 的 $0^m 1^n$ 字符串，以及所有格式错误的字符串。
   • $L_{all}$ 包含所有格式正确的 $0^m 1^n$ 字符串。
   • 这两者的交集，就会过滤掉所有格式错误的字符串，只剩下那些格式正确（来自 $L_{all}$）且满足 $m=n$（来自 $L_1^c$）的字符串。
   • 这正是 $L_{eq}$ 的定义！所以 $L_{eq} = L_1^c \cap L_{all}$。
5. 推导出矛盾：
   • 我们假设 $L_1$ 是正则的。
   • 那么 $L_1^c$ 也是正则的（补集封闭性）。
   • $L_{all}$ 是已知的正则语言。
   • 正则语言对交集运算也是封闭的。所以 $L_1^c \cap L_{all}$ 必须是正则的。
   • 这意味着 $L_{eq}$ 必须是正则的。
   • 但这与我们已知的“$L_{eq}$ 是非正则的”这个事实相矛盾。
6. 得出结论: 矛盾的根源在于我们最初的假设。因此，假设“$L_1$ 是正则的”是错误的。结论：$L_1$ 非正则。

这是第三种证明方法，使用了 Myhill-Nerode 定理。这个定理提供了一个判断语言是否正则的充要条件。

Myhill-Nerode 定理的核心思想是等价关系 $\sim_L$。对于一个语言 $L$，如果两个字符串 $x$ 和 $y$ 在后面无论追加任何相同的字符串 $z$ 后，得到的新字符串 $xz$ 和 $yz$ 的“命运”总是相同（即要么都属于 $L$，要么都不属于 $L$），我们就说 $x$ 和 $y$ 是不可区分的，记为 $x \sim_L y$。

• 可区分: 如果能找到至少一个字符串 $z$（称为区分扩展），使得 $xz$ 和 $yz$ 一个在 $L$ 中，另一个不在，那么 $x$ 和 $y$ 就是可区分的，记为 $x \not\sim_L y$。
• 等价类: 所有相互不可区分的字符串构成一个等价类。
• 定理内容: 一个语言 $L$ 是正则的，当且仅当由关系 $\sim_L$ 产生的等价类数量是有限的。这个数量也恰好是识别 $L$ 的最小 DFA 的状态数。

这个证明的策略是：找到一个无限的字符串集合，并证明这个集合中的任意两个不同的字符串都是相互可区分的。如果能做到，就说明每个字符串都至少属于一个不同的等gaoj类，从而证明等价类的数量是无限的。

1. 选择无限集合: 我们选择集合 $S = \{0^q \mid q \ge 0\} = \{\epsilon, 0, 00, 000, \dots\}$。这是一个无限集。
2. 证明互相可区分: 我们需要证明，对于 $S$ 中的任意两个不同的字符串，比如 $0^q$ 和 $0^r$ (假设 $q \neq r$)，它们都是可区分的。
3. 寻找区分扩展:
   • 取两个不同的前缀：$x = 0^q$ 和 $y = 0^r$。
   • 我们需要找到一个后缀 $z$，使得 $xz$ 和 $yz$ 的命运不同。
   • 证明中选择 $z = 1^q$。
4. 验证:
   • 将 $z$ 追加到 $x$ 后面：$xz = 0^q 1^q$。在这个字符串中，0 的数量和 1 的数量相等 ($q=q$)。根据 $L_1$ 的定义 ($n \neq m$)，$0^q 1^q$ 不属于 $L_1$。
   • 将 $z$ 追加到 $y$ 后面：$yz = 0^r 1^q$。在这个字符串中，0 的数量是 $r$，1 的数量是 $q$。因为我们一开始就假设了 $q \neq r$，所以这个字符串属于 $L_1$。
5. 得出结论: 我们找到了一个区分扩展 $z=1^q$，它使得 $0^q z \notin L_1$ 而 $0^r z \in L_1$。这证明了 $0^q$ 和 $0^r$ 是可区分的 ($0^q \not\sim_{L_1} 0^r$)。
6. 推广: যেহেতু $q$ 和 $r$ 是任意两个不同的非负整数，这意味着集合 $S = \{\epsilon, 0, 00, 000, \dots\}$ 中的每一个字符串都与其他所有字符串可区分。因此，它们必须属于不同的等价类。
7. 应用定理: 因为我们找到了一个无限的、两两可区分的字符串集合，所以 $\sim_{L_1}$ 关系必然有无限个等价类。根据 Myhill-Nerode 定理，如果等价类数量是无限的，则语言非正则。

这部分证明语言 $L_2 = \{ww \mid w \in \{a, b\}^*\}$ 是非正则的。这个语言由任意一个 $\{a, b\}$ 上的字符串 $w$ 和它自身的精确拷贝连接而成。例如 abab, aaaa, ababaabab 都在 $L_2$ 中。直觉上，为了验证一个字符串是否为 $ww$ 形式，机器需要读完前半部分，记住它，然后精确匹配后半部分。这需要无限的记忆力。

该证明使用了泵引理。

1. 假设 $L_2$ 是正则的: 开始反证法。
2. 泵长度: 根据假设，存在一个泵长度 $p$。
3. 选择字符串: 我们选择 $w = a^p b a^p b$。
   • 这个字符串属于 $L_2$ 吗？是的。它是由子串 $w' = a^p b$ 和它自身的拷贝组成的，即 $(a^p b)(a^p b)$。
   • 它的长度是 $2p+2$，当 $p \ge 1$ 时，长度大于 $p$。
4. 对手的分割: 泵引理保证可以将 $w$ 分割为 $xyz$，满足：
   • $|xy| \le p$
   • $|y| > 0$
   • $xy^iz \in L_2$ for all $i \ge 0$.
5. 分析分割:
   • 字符串 $w$ 的开头是 $p$ 个 $a$。
   • 因为 $|xy| \le p$，所以 $x$ 和 $y$ 字符串必须完全位于这开头的 $p$ 个 $a$ 之中。
   • 因为 $|y|>0$，$y$ 必须是至少一个 $a$。
   • 所以，$y$ 的形式是 $a^k$，其中 $1 \le k \le p$。
   • $x$ 的形式是 $a^{p-k-j}$，$z$ 的形式是 $a^j b a^p b$ 的一部分，但更具体的写法是 $x=a^{p_1}, y=a^k, z=a^{p_2}ba^pb$ 其中 $p_1+k+p_2=p$。
6. 泵送并寻找矛盾:
   • 原文选择泵送 $i=3$。（泵送 $i=2$ 或 $i=0$ 也可以）。
   • 泵送后的字符串 $w' = xy^3z$。
   • 原来的 0 的数量是 $p = p_1+k+p_2$。泵送后，y 被复制了 3 次，所以 0 的数量变成了 $p_1+3k+p_2 = p+2k$。
   • 所以 $w' = a^{p+2k} b a^p b$。
   • 现在我们来判断 $w'$ 是否还在 $L_2$ 中。$L_2$ 的字符串必须是 $u u$ 的形式，这意味着它的长度必须是偶数，并且前半部分和后半部分完全一样。
   • $w'$ 的长度是 $(p+2k)+1+p+1 = 2p+2k+2$。这是一个偶数。
   • 它的前半部分是 $u_1 = a^{p+k+1}$ (这里原文的分析 $a^{p+2k} b a^{p} b$ 是对整个字符串的描述，为了检查 $uu$ 形式，我们需要将其对半分。它的长度是 $2p+2k+2$，所以中点在第 $p+k+1$ 个字符之后)。前半部分的长度是 $p+k+1$。
   • $w' = a^{p+2k} b a^p b$。前半部分 $u_1$ 是 $a^{p+k+1}$。后半部分 $u_2$ 是 $a^{k-1}ba^pb$。
   • $u_1$ 只包含 $a$，$u_2$ 包含 $b$。显然 $u_1 \neq u_2$。
   • 更简单的分析：$w'$ 的形式是 $a..ab a..ab$。第一个 $b$ 出现在第 $p+2k+1$ 个位置。而 $w$ 的中点在第 $p+1$ 个位置。泵送后，第一个 $b$ 的位置移动了，但第二个 $b$ 的位置没动。这破坏了对称结构。$a^{p+2k} b a^{p} b$ 无法写成 $uu$ 的形式。
   • 因此，$w'$ 不在 $L_2$ 中。
7. 结论: 我们找到了一个 $i=3$，使得 $xy^iz \notin L_2$。这与泵引理的要求相矛盾。因此，最初的假设是错误的，$L_2$ 非正则。

这个证明比泵引理更直接，也更深刻。它直接攻击了正则语言有限等价类的核心性质。

1. 目标: 证明 $L_2$ 有无限个等价类。
2. 策略: 证明在字母表 $\{a,b\}^*$ 上，任意两个不同的字符串 $w$ 和 $s$ ($w \neq s$) 都是可区分的。如果能做到这一点，那么每个字符串都自成一个等价类，而 $\{a,b\}^*$ 中的字符串是无限多的，所以等价类也是无限多的。
3. 选择任意两个不同字符串: 设 $w, s \in \{a,b\}^*$ 且 $w \neq s$。
4. 寻找区分扩展:
   • 我们选择 $z=w$ 作为区分扩展。
   • 将 $z$ 追加到第一个字符串 $w$ 后面：得到 $wz = ww$。根据 $L_2$ 的定义，这个新字符串属于 $L_2$。
   • 将 $z$ 追加到第二个字符串 $s$ 后面：得到 $sz = sw$。因为 $s \neq w$，所以这个新字符串不满足 $uu$ 的形式，因此它不属于 $L_2$。
5. 得出结论: 我们找到了一个区分扩展 $z=w$，它成功地区分了 $w$ 和 $s$。一个追加后在语言里，一个不在。
6. 推广: 由于我们的选择 $w$ 和 $s$是任意的，这个逻辑适用于 $\{a,b\}^*$ 中任何一对不同的字符串。例如，a 和 b 是可区分的，ab 和 aba 是可区分的，等等。
7. 应用定理: 既然 $\{a,b\}^*$ 中无限多的字符串两两之间都是可区分的，那么 $\sim_{L_2}$ 关系必然有无限个等价类。根据 Myhill-Nerode 定理，$L_2$ 非正则。

这部分证明语言 $L_3 = \{1^{2^n} \mid n \ge 0\}$ 是非正则的。这个语言的字符串只由 '1' 组成，其长度必须是 2 的幂 (e.g., $1^1, 1^2, 1^4, 1^8, \dots$)。

证明使用了泵引理。

1. 假设 $L_3$ 是正则的。
2. 泵长度: 存在一个泵长度 $p$。
3. 选择字符串: 我们选择 $w = 1^{2^p}$。
   • 这个字符串在 $L_3$ 中，因为它的长度是 $2^p$ (取 $n=p$)。
   • 它的长度 $|w| = 2^p$。我们需要确保 $2^p \ge p$。对于所有 $p \ge 1$，$2^p > p$ 这个不等式都成立 (可以通过数学归纳法证明)。所以字符串足够长。
4. 对手的分割: $w$ 被分割为 $xyz$。
   • $w$ 完全由 '1' 组成，所以 $x,y,z$ 都只能是 '1' 的字符串。设 $|x|=a, |y|=b, |z|=c$。
   • 规则：$a+b+c = 2^p$ (总长), $|xy| = a+b \le p$ (分割点靠前), $|y|=b > 0$ (泵送部分非空)。
5. 泵送并寻找矛盾:
   • 我们选择泵送 $i=2$ (向上泵送一次)。
   • 新字符串 $w' = xy^2z$。
   • 新字符串的长度 $|w'| = |x| + 2|y| + |z| = a+2b+c = (a+b+c) + b = 2^p + b$。
6. 分析新长度:
   • 我们要证明 $|w'|$ 不可能是 2 的幂。
   • 我们知道 $b > 0$ (根据 $|y|>0$)，所以 $2^p+b > 2^p$。
   • 我们还知道 $b \le a+b \le p$ (根据 $|xy| \le p$)，所以 $b \le p$。
   • 因此，新长度 $|w'| = 2^p+b \le 2^p+p$。
   • 下一个 2 的幂是 $2^{p+1}$。我们来比较 $2^p+p$ 和 $2^{p+1}$。
   • $2^{p+1} = 2 \times 2^p = 2^p + 2^p$。
   • 因为我们知道 $p < 2^p$ (对于 $p \ge 1$)，所以 $2^p+p < 2^p+2^p = 2^{p+1}$。
   • 把这些不等式串起来，我们得到：$2^p < |w'| \le 2^p+p < 2^{p+1}$。
   • 这个不等式链说明 $|w'|$ 的值严格地卡在两个连续的 2 的幂 ($2^p$ 和 $2^{p+1}$) 之间。
   • 因此，$|w'|$ 本身不可能是 2 的幂。
7. 结论: 泵送后的字符串 $w'$ 不在 $L_3$ 中。这与泵引理的要求（$xy^2z$ 必须在 $L_3$ 中）相矛盾。所以原始假设是错误的，$L_3$ 非正则。

这个证明再次使用了 Myhill-Nerode 定理。策略是选取 $L_3$ 语言自身这个无限集合，并证明其中任意两个不同的字符串都是可区分的。

1. 目标: 证明 $L_3$ 有无限个等价类。
2. 选择无限集合: 我们选择 $S = L_3 = \{1^{2^n} \mid n \ge 0\} = \{1^1, 1^2, 1^4, \dots\}$。
3. 证明互相可区分:
   • 取 $S$ 中任意两个不同的字符串，设为 $x=1^{2^m}$ 和 $y=1^{2^n}$。不失一般性，假设 $m < n$。
4. 寻找区分扩展:
   • 证明中选择 $z=1^{2^m}$ 作为区分扩展 (即，选择两个字符串中较短的那一个作为后缀)。
5. 验证:
   • 将 $z$ 追加到 $x$ 后面：$xz = 1^{2^m} 1^{2^m}$。新字符串的长度是 $2^m + 2^m = 2 \times 2^m = 2^{m+1}$。因为 $m+1$ 是一个整数，所以这个长度是 2 的幂。因此，$xz \in L_3$。
   • 将 $z$ 追加到 $y$ 后面：$yz = 1^{2^n} 1^{2^m}$。新字符串的长度是 $2^n + 2^m$。
6. 分析新长度 $2^n + 2^m$:
   • 因为 $m < n$，所以 $2^m < 2^n$。
   • 所以，我们有不等式 $2^n < 2^n + 2^m$。
   • 同时，我们有 $2^n + 2^m < 2^n + 2^n = 2 \times 2^n = 2^{n+1}$。
   • 将不等式串联：$2^n < |yz| < 2^{n+1}$。
   • 这个长度 $|yz|$ 严格地卡在两个连续的 2 的幂之间，所以它本身不可能是 2 的幂。因此，$yz \notin L_3$。
7. 得出结论: 我们找到了一个区分扩展 $z=1^{2^m}$，它使得 $xz \in L_3$ 而 $yz \notin L_3$。这证明了 $1^{2^m}$ 和 $1^{2^n}$ 是可区分的。
8. 推广: যেহেতু $m$ 和 $n$ 可以是任意两个不同的非负整数，这表明 $L_3$ 中所有的字符串都是两两可区分的。
9. 应用定理: $L_3$ 是一个无限集，且其中元素两两可区分，这意味着必然存在无限个等价类。根据 Myhill-Nerode 定理，$L_3$ 非正则。

这部分定义了一个更为复杂的语言 $L_4$。它的结构依赖于前缀 c 的数量的奇偶性。

• 结构: 字符串由两部分组成：前缀 $c^n$（$n$ 个 $c$）和后缀 $w$（由 $a,b$ 组成）。
• 条件:
• 如果 $n$ 是偶数（包括 $n=0$），对 $w$ 没有任何要求。任何 $\{a,b\}^*$ 上的字符串 $w$ 都是可以的。
• 如果 $n$ 是奇数，则 $w$ 必须是一个回文（palindrome），即 $w$ 从前向后读和从后向前读是一样的 ($w=w^R$)。

接着，它抛出了一个非常重要的结论：$L_4$ 是一个非正则语言，但它却满足泵引理的条件。这意味着我们无法使用泵引理来证明它的非正则性。这是泵引理的一个局限性：泵引理是正则语言的必要非充分条件。即：

• 如果一个语言是正则的，它一定满足泵引理。
• 如果一个语言不满足泵引理，它一定是非正则的。
• 如果一个语言满足泵引理，它可能是正则的，也可能是非正则的。$L_4$ 就是后者的例子。

最后，预告了将首先解释为什么泵引理会失效，然后用 Myhill-Nerode 定理和封闭性来证明其非正则性。

这部分的核心是证明 $L_4$ 满足泵引理，从而说明泵引理无法用于证明其非正则性。这里的角色发生了转换：我们不再是试图制造矛盾的“攻击者”，而是扮演“防御者”，为泵引理找到一个永远不会导致矛盾的划分方案。

我们将泵长度设为 $p=2$。我们需要为任何长度 $\ge 2$ 的 $w' \in L_4$ 找到一个“安全”的划分。

令 $w' = c^n w$。

情况 1: $n$ 是奇数

• 此时 $w$ 是一个回文。字符串是 $c^n w$。
• 我们选择的划分是：$x=\epsilon$ (空串)，$y=c$ (第一个 $c$)，$z=c^{n-1}w$ (余下部分)。
• 这个划分满足泵引leem的前两个条件：$|xy|=1 \le p=2$，$|y|=1>0$。
• 现在泵送 $y$：新字符串是 $xy^iz = \epsilon c^i (c^{n-1}w) = c^{n+i-1}w$。
• 我们检查这个新字符串是否总在 $L_4$ 中：
• 新的 $c$ 的数量是 $n' = n+i-1$。后缀 $w$ 保持不变。
• 如果 $n'$ 是偶数：根据 $L_4$ 的定义，对后缀没有要求。新字符串 $c^{n'}w$ 属于 $L_4$。
• 如果 $n'$ 是奇数：根据 $L_4$ 的定义，后缀必须是回文。我们的后缀 $w$ 本身就是一个回文（因为原始的 $n$ 是奇数）。所以新字符串 $c^{n'}w$ 属于 $L_4$。
• 结论：无论泵送多少次，新字符串的 $c$ 个数要么是偶数（自动满足条件），要么是奇数（而后缀 $w$ 恰好是回文，也满足条件）。所以 $xy^iz$ 永远在 $L_4$ 中。矛盾无法产生。

情况 2: $n$ 是偶数

• 此时对 $w$ 没有要求。
• 子情况 2.1: $n=0$
• 字符串是 $w$ (来自 $\{a,b\}^*$)，长度 $\ge 2$。
• 我们划分 $x=\epsilon$，$y$是 $w$ 的前两个字符，$z$ 是 $w$ 的剩余部分。$|xy|=2 \le p=2, |y|=2>0$。
• 泵送后，新字符串 $xy^iz$ 仍然只包含 $a, b$。
• 这个新字符串的 $c$ 的数量是 0，是偶数。根据 $L_4$ 定义，对后缀没有要求。所以新字符串永远在 $L_4$ 中。矛盾无法产生。
• 子情况 2.2: $n \ge 2$ (偶数)
• 字符串是 $c^n w$，长度 $\ge 2$。
• 我们划分 $x=\epsilon$，$y=cc$ (前两个 $c$)，$z=c^{n-2}w$。
• 这个划分满足 $|xy|=2 \le p=2, |y|=2>0$。
• 泵送 $y$：新字符串 $xy^iz = (cc)^i c^{n-2}w = c^{2i}c^{n-2}w = c^{n+2i-2}w = c^{n+2(i-1)}w$。
• 新的 $c$ 的数量是 $n' = n+2(i-1)$。
• 因为 $n$ 是偶数，$2(i-1)$ 也是偶数，所以 $n'$ 永远是偶数。
• 根据 $L_4$ 定义，当 $c$ 的数量是偶数时，对后缀没有要求。所以新字符串永远在 $L_4$ 中。矛盾无法产生。

总结: 我们已经证明，对于 $L_4$ 中任何足够长的字符串，我们总能找到一种“安全”的泵送方式（通常是泵送开头的 $c$），使得泵送后的字符串永远不会违反 $L_4$ 的规则。因此，泵引理无法用来证明 $L_4$ 非正则。

这个证明回归到了更强大的 Myhill-Nerode 定理。

1. 目标: 证明 $L_4$ 有无限个等价类。
2. 策略: 找到一个无限的字符串集合，并证明其中任意两个不同的字符串都是相互可区分的。
3. 选择无限集合: 我们选择集合 $S = \{ca^n \mid n \ge 0\} = \{c, ca, caa, caaa, \dots\}$。这是一个无限集。
4. 证明互相可区分:
   • 取 $S$ 中任意两个不同的字符串，设为 $x=ca^n$ 和 $y=ca^m$，其中 $n \neq m$。
5. 寻找区分扩展:
   • 我们的目标是找到一个后缀 $z$，追加到 $x$ 和 $y$ 之后，使得一个结果在 $L_4$ 中，另一个不在。
   • 证明中选择 $z = b a^n$。这个选择非常巧妙，因为它试图用 $a^n$ 来“完成” $x=ca^n$ 的回文结构。
6. 验证:
   • 将 $z$ 追加到 $x$ 后面：$xz = (ca^n)(ba^n) = c(a^n b a^n)$。
   • 分析这个新字符串：前缀是 $c^1$ (1是奇数)。后缀是 $w' = a^n b a^n$。
   • $w'$ 是回文吗？是的，它的逆 $ (a^n b a^n)^R = (a^n)^R b^R (a^n)^R = a^n b a^n = w'$。
   • 因为 $c$ 的数量是奇数，且后缀是回文，所以 $xz \in L_4$。
   • 将 $z$ 追加到 $y$ 后面：$yz = (ca^m)(ba^n) = c(a^m b a^n)$。
   • 分析这个新字符串：前缀是 $c^1$ (1是奇数)。后缀是 $w'' = a^m b a^n$。
   • $w''$ 是回文吗？不是。因为 $m \neq n$，$w''$ 的逆是 $a^n b a^m$，不等于 $w''$。
   • 因为 $c$ 的数量是奇数，但后缀不是回文，所以 $yz \notin L_4$。
7. 得出结论: 我们找到了一个区分扩展 $z=ba^n$，它成功地区分了 $ca^n$ 和 $ca^m$。
8. 推广和应用定理: 因为这适用于任何 $n \neq m$，所以集合 $S$ 中的所有字符串都是两两可区分的。这意味着存在无限个等价类。根据 Myhill-Nerode 定理，$L_4$ 非正则。

这个证明结合了封闭性和泵引理，是一种“先简化，再攻击”的策略。

1. 假设 $L_4$ 是正则的。
2. 引入一个简单的正则语言: 定义 $L_5 = \{cw \mid w \in \{a,b\}^*\}$。这个语言描述了所有以一个 c 开头，后面跟着任意 $a,b$ 字符串的语言。它的正则表达式是 c(a|b)*。因为它可以被正则表达式描述，所以 $L_5$ 是正则的。
3. 应用封闭性:
   • 我们假设了 $L_4$ 是正则的。
   • 我们知道 $L_5$ 是正则的。
   • 正则语言在交集运算下是封闭的。
   • 所以，它们的交集 $L_r = L_4 \cap L_5$ 也必须是正则的。
4. 分析交集 $L_r$:
   • $L_4$ 的字符串是 $c^n w$，其中如果 $n$ 奇数则 $w$ 是回文，如果 $n$ 偶数则 $w$ 任意。
   • $L_5$ 的字符串是 $c^1 w$，即 $n$ 必须等于 1。
   • 那么，$L_4 \cap L_5$ 就是同时满足这两个条件的字符串。这意味着 $n$ 必须是 1。而 1 是一个奇数，所以 $L_4$ 对后缀 $w$ 的要求是 “$w$ 必须是回文”。
   • 因此，$L_r = \{cw \mid w \in \{a,b\}^*, w=w^R\}$。这个语言由一个 c 开头，后面跟着一个任意长度的 $a,b$ 回文组成。
5. 攻击简化后的语言:
   • 现在我们有了一个更简单的语言 $L_r$，并且从逻辑上推断出如果 $L_4$ 正则则 $L_r$ 也正则。
   • 接下来，我们证明 $L_r$ 是非正则的。这可以很容易地用泵引理证明（这几乎是证明回文语言非正则的标准练习）。
   • 证明 $L_r$ 非正则（简略）:
   • 设 $p$ 为泵长度。
   • 选字符串 $s = c a^p b a^p \in L_r$。
   • 泵引理要求泵送 $y$。因为 $|xy| \le p$，这里 $p$ 是 $L_r$ 的泵长度，但我们选的字符串 $s$ 的第一个字符是 $c$。如果我们选的泵长度 $p \ge 2$，那么泵送就会发生在 $a^p$ 上。
   • 选 $s = c a^p b a^p \in L_r$。$|s| = 2p+2$。假设 $p \ge 1$。
   • 根据泵引理，可分割 $s=xyz$。但 $|xy| \le p$ 这条规则是针对 $L_r$ 的泵长度 $p_r$ 的。
   • 让我们用标准的回文证明。令 $L_{pal} = \{w \mid w=w^R\}$。我们知道它是非正则的。$L_r = \{c\} \cdot L_{pal}$。一个正则语言和一个非正则语言的连接不一定是非正则的。所以这个论证需要更小心。
   • 回到原文的思路：用泵引理证明 $L_r = \{ca^pba^p\}$。设 $p_r$ 是 $L_r$ 的泵长度。选择 $s = c a^{p_r} b a^{p_r}$。$|s| > p_r$。$s \in L_r$。泵引理分割 $s=xyz$。因为 $|xy| \le p_r$，且 $s$ 以 $c$ 开头，如果 $p_r=1$，y只能是 $c$。泵送 $i=2$ 得到 $cc a^1 b a^1$，不在 $L_r$ 中。如果 $p_r > 1$，$y$ 会是 $a^k$。泵送后得到 $c a^{p_r+k} b a^{p_r}$，不再是回文。所以 $L_r$ 非正则。
6. 得出矛盾:
   • 我们的假设（$L_4$ 正则） $\implies$ $L_r$ 正则。
   • 我们独立的证明显示 $L_r$ 非正则。
   • 这是一个矛盾。