1. 讲义标题与元信息

这部分内容是讲义的元信息，用于标识课程、讲师、发布日期以及本讲义的主题。

• COMS W3261: 这是课程代码，代表哥伦比亚大学计算机科学系的 W3261 课程，课程名称是“计算机理论”。
• 讲师：Tal Malkin: 指明了授课教授的名字。
• 日期：2024 年 9 月: 表明了这份讲义发布或适用的时间。
• 讲义 3：Myhill-Nerode 定理及其影响: 这是讲义的标题，明确指出了本讲义的核心内容是 Myhill-Nerode 定理 以及由该定理引申出的相关概念和应用（即“其影响”）。

这段话是整篇讲义的引言，旨在告诉我们 Myhill-Nerode 定理是什么，以及它为什么重要。

1. “Myhill-Nerode 定理是正则语言理论中的一个基本结果。”
   • 这句话给定了定理的领域和地位。它不属于某个偏僻的角落，而是计算理论中关于正则语言这一核心分支的基础性、关键性成果。
2. “它提供了正则语言的一个特征刻画”
   • “特征刻画”（Characterization）是一个很强的数学术语。它的意思是，这个定理提供了一个与“正则语言”完全等价的条件。也就是说，“一个语言是正则的” 当且仅当 “它满足 Myhill-Nerode 定理描述的某个性质”。这就像说“一个整数是偶数”的特征刻画是“它能被2整除”。这两件事是完全等价的。
3. “因此可以用来证明一个语言 $L$ 是否是正则的。”
   • 这是特征刻画带来的第一个直接应用。因为有了一个等价条件，我们就有了一个新的工具（除了 DFA、NFA、正则表达式、泵引理之外）来判断一个语言的正则性。
   • 证明一个语言是正则的：证明它满足 Myhill-Nerode 定理的条件。
   • 证明一个语言不是正则的：证明它不满足 Myhill-Nerode 定理的条件。
4. “如果 $L$ 是正则的，它还可以用来寻找识别 $L$ 的 DFA 中的最小状态数。”
   • 这是定理的第二个重要应用。它不仅能判断“是或不是”，还能给出“是多少”的答案。对于一个正则语言，总存在一个识别它的、拥有最少状态的 DFA，我们称之为最小 DFA。Myhill-Nerode 定理能精确地告诉我们这个最小状态数是多少。这对于设计最高效的机器非常重要。
5. “事实上，这个定理是高效 DFA 最小化算法的核心。”
   • 这揭示了该定理在实践中的价值。存在一些算法，可以将一个任意的、可能有很多冗余状态的 DFA，转化为一个状态最少的等价 DFA。这些算法的理论基础正是 Myhill-Nerode 定理。
6. “在这里，我们介绍 Myhill-Nerode 定理，并给出一些将其应用于正则和非正则语言的例子。”
   • 这句话预告了本讲义的结构：首先会介绍定理本身，然后通过具体的例子来展示如何使用它。

这部分内容提供了学术诚信信息和课程定位。

1. 致谢与来源: 第一段话说明了这份讲义的知识来源，是对前人工作的致谢，体现了学术严谨性。同时，它也为感兴趣的学生提供了进一步的参考资料：
   • Sipser 的教科书: 经典教材《计算理论导引》，定理在习题中出现，说明它在某些教学体系中被视为进阶或拓展内容。
   • Hopcroft, Motwani, Ullman 的教科书: 另一本经典教材《自动机理论、语言和计算导论》（俗称“龙书”），其中有更详细的章节，说明这是深入学习的好去处。
2. 课程要求: 第二段明确了该定理在 COMS W3261 这门课中的地位。
   • 推荐阅读: 这不是强制要求掌握的内容，而是作为补充材料。
   • 可以使用: 虽然不强制，但学了就可以在作业和考试中用。这给了学生一个选择，可以用更强大的工具解决问题。
   • 不属于必修内容: 考试不会专门出一道题考“请陈述 Myhill-Nerode 定理”，课程的后续内容也不会基于你已经学会这个定理的前提来展开。这为不想深入这部分的同学减轻了负担。

这是 Myhill-Nerode 定理的基石。整个定理都建立在这个定义之上。让我们一步步拆解它。

1. “令 $L \subseteq \Sigma^{*}$ 为字母表 $\Sigma$ 上的任意语言。”
   • 这设定了舞台。我们讨论的是一个语言 $L$。这个语言是基于某个字母表 $\Sigma$ 的。例如，$\Sigma = \{0, 1\}$，那么 $L$ 就是一个由0和1组成的字符串的集合。
2. “对于 $x, y \in \Sigma^{*}$”
   • 我们从这个字母表能构成的所有字符串（$\Sigma^{*}$）中，任意挑选两个字符串，称它们为 $x$ 和 $y$。
3. “如果 $x z$ 和 $y z$ 中恰好有一个在 $L$ 中”
   • 这是核心判断标准。我们现在要找第三个字符串 $z$（$z$ 也可以是空字符串 $\epsilon$）。
   • 我们把 $z$ 分别拼接到 $x$ 和 $y$ 的后面，形成两个新字符串 $xz$ 和 $yz$。
   • 然后我们检查这两个新字符串的“命运”：
   • $xz \in L$ 并且 $yz \notin L$ （$xz$ 在语言里，$yz$ 不在）
   • 或者 $xz \notin L$ 并且 $yz \in L$ （$xz$ 不在语言里，$yz$ 在）
   • 只要满足上述两种情况之一（即它们的成员身份不一致），我们就找到了一个特殊的 $z$。
4. “我们称 $z \in \Sigma^{*}$ 为 $x$ 和 $y$ 的区别扩展。”
   • 那个能让 $x$ 和 $y$ “命运”分离的字符串 $z$，就被赋予了一个名字，叫做“区别扩展”（Distinguishing Extension）。
5. “如果存在这样的 $z$，我们说 $x$ 和 $y$ 对于 $L$ 是可区分的”
   • 我们不需要检查所有的 $z$。只要能找到至少一个这样的 $z$，我们就可以立刻下结论：$x$ 和 $y$ 是可区分的（Distinguishable）。
6. “否则，我们说 $x$ 和 $y$ 对于 $L$ 是不可区分的。”
   • “否则”指的是什么情况？指的是我们找不到任何一个这样的 $z$。
   • 也就是说，对于任意的字符串 $z \in \Sigma^{*}$，$xz$ 和 $yz$ 的命运总是相同的：要么它们都在 $L$ 中，要么它们都不在 $L$ 中。
   • 只有在这种情况下，我们才能说 $x$ 和 $y$ 是不可区分的（Indistinguishable）。

这段话解释了上一节定义的“直觉”目的，也就是它和 DFA 的关系。

1. “如果两个字符串 $x, y$ 对于 $L$ 是可区分的，那么...DFA...必须结束于两个不同的状态。”
   • 这是核心论点。可区分性（语言的属性）直接映射到 DFA 的物理结构（状态的分离）。
   • 为什么？让我们用反证法来理解。
2. “这是因为如果 $x$ 和 $y$ 到达 DFA 中的同一个状态...”
   • 假设，为了找到矛盾，我们假设 $x$ 和 $y$ 是可区分的，但一个 DFA $M$ 在读取完 $x$ 和 $y$ 之后，都到达了同一个状态，我们叫它 $q$。
   • 形式化地说，$\delta^*(q_0, x) = q$ 并且 $\delta^*(q_0, y) = q$。
3. “...那么对于任何扩展 $z$，$x z$ 和 $y z$ 将到达同一个状态。”
   • 这是 DFA 的本性决定的。DFA 是“确定性的”，它的后续行为只取决于当前状态和后续输入，与如何到达当前状态的历史无关。
   • 既然从 $q$ 开始，输入相同的字符串 $z$，那么无论当初是通过 $x$ 还是 $y$ 到达的 $q$，最终到达的状态必然是相同的。
   • 形式化地说，$\delta^*(q, z)$ 的结果是唯一的。因此 $\delta^*(q_0, xz) = \delta^*(\delta^*(q_0, x), z) = \delta^*(q, z)$ 和 $\delta^*(q_0, yz) = \delta^*(\delta^*(q_0, y), z) = \delta^*(q, z)$ 会是同一个结束状态。
4. 矛盾的产生:
   • 如果 $xz$ 和 $yz$ 总是结束在同一个状态，那么这个状态要么是接受状态，要么不是。
   • 这意味着 DFA $M$ 要么同时接受 $xz$ 和 $yz$，要么同时拒绝它们。
   • 但这与我们最初的假设“$x$ 和 $y$ 是可区分的”相矛盾！因为“可区分”意味着存在一个 $z$，使得 $xz$ 和 $yz$ 一个被接受，一个被拒绝。
   • 既然假设“$x$ 和 $y$ 到达同一个状态”会导致矛盾，那么这个假设一定是错误的。
5. 结论:
   • 因此，如果 $x$ 和 $y$ 是可区分的，任何能正确识别该语言的 DFA 都必须将它们映射到不同的状态。

这个引理是上一段逻辑的直接推论和量化。

1. “假设存在一个包含 $k$ 个不同字符串的集合 $\left\{x_{1}, \ldots, x_{k}\right\}$”
   • 我们找到了一个特殊的小团体，里面有 $k$ 个字符串。
2. “使得对于任何 $i \neq j$，$x_{i}$ 和 $x_{j}$ 对于 $L$ 是可区分的。”
   • 这个小团体的特殊之处在于，里面任意挑出两个不同的成员，它俩都是相互可区分的。我们称这样的集合为一个“两两可区分集”(pairwise distinguishable set)。
3. “那么不存在状态数少于 $k$ 且识别 $L$ 的 DFA。”
   • 这是结论。这个结论给出了识别 $L$ 的 DFA 的状态数量的一个下界。
   • 换句话说，任何能够识别 $L$ 的 DFA，其状态数量至少为 $k$。
   • 为什么？这可以用鸽巢原理 (Pigeonhole Principle) 来简单说明。

证明思路:

• 我们有 $k$ 个字符串 $x_1, \ldots, x_k$。把它们看作 $k$ 个“鸽子”。
• 假设我们有一个识别 $L$ 的 DFA，它有 $m$ 个状态。把这些状态看作 $m$ 个“鸽巢”。
• DFA 在处理完每个字符串 $x_i$ 后，会到达一个状态 $\delta^*(q_0, x_i)$。
• 根据上一节的结论，因为 $x_i$ 和 $x_j$ (对于 $i \neq j$) 是可区分的，所以它们必须到达不同的状态。即 $\delta^*(q_0, x_i) \neq \delta^*(q_0, x_j)$。
• 这意味着，我们的 $k$ 个“鸽子” ($x_1, \ldots, x_k$) 必须飞进 $k$ 个不同的“鸽巢”（状态）。
• 因此，鸽巢的数量（状态数 $m$）必须至少等于鸽子的数量（字符串数 $k$）。
• 所以，$m \ge k$。
• 这就证明了，状态数不可能少于 $k$。

这部分引入了一个新的符号 $\sim_L$，并指出了它所代表的“不可区分性”关系具有一个非常重要的数学性质——它是一个等价关系。

1. 定义 $\sim_L$:
   • 我们用一个简洁的符号 $x \sim_L y$ 来表示“$x$ 和 $y$ 对于语言 $L$ 是不可区分的”。
   • 回忆一下不可区分的定义：对于所有的字符串 $z \in \Sigma^*$，都有 $xz \in L \iff yz \in L$。
2. 什么是等价关系？
   • 在数学上，一个关系（比如“=”, “<”, “是...的朋友”）如果同时满足以下三个性质，就被称为等价关系：
   • 自反性 (Reflexivity): 任何元素都与它自身有关系。 $a \sim a$.
   • 对称性 (Symmetry): 如果 $a$ 与 $b$ 有关系，那么 $b$ 也与 $a$ 有关系。 $a \sim b \implies b \sim a$.
   • 传递性 (Transitivity): 如果 $a$ 与 $b$ 有关系，且 $b$ 与 $c$ 有关系，那么 $a$ 也与 $c$ 有关系。 $a \sim b \land b \sim c \implies a \sim c$.
   • 最经典的等价关系是“等于号 =”。
3. 证明 $\sim_L$ 是等价关系:
   • 自反性 ($x \sim_L x$):
   • 我们需要证明 $x$ 和 $x$ 是不可区分的。
   • 根据定义，我们要检查对于所有 $z$，$xz \in L \iff xz \in L$ 是否成立。
   • 这是一个逻辑上的重言式（A if and only if A），它永远为真。
   • 所以，$\sim_L$ 满足自反性。
   • 对称性 ($x \sim_L y \implies y \sim_L x$):
   • 假设 $x \sim_L y$。这意味着对于所有 $z$，$xz \in L \iff yz \in L$。
   • 逻辑上的“当且仅当”($\iff$)关系本身就是对称的。如果 (A $\iff$ B) 成立，那么 (B $\iff$ A) 也成立。
   • 所以，对于所有 $z$，$yz \in L \iff xz \in L$ 也成立。
   • 这正是 $y \sim_L x$ 的定义。
   • 所以，$\sim_L$ 满足对称性。
   • 传递性 ($x \sim_L y \land y \sim_L w \implies x \sim_L w$):
   • 假设 $x \sim_L y$ 并且 $y \sim_L w$。
   • $x \sim_L y$ 意味着：对所有 $z$, ($xz \in L \iff yz \in L$)。 (关系1)
   • $y \sim_L w$ 意味着：对所有 $z$, ($yz \in L \iff wz \in L$)。 (关系2)
   • 我们要证明 $x \sim_L w$，即对于所有 $z$，$xz \in L \iff wz \in L$。
   • 从关系1和关系2，我们可以看到 $xz \in L$ 的“命运”和 $yz \in L$ 的“命运”是绑定的，而 $yz \in L$ 的“命运”又和 $wz \in L$ 的“命运”是绑定的。
   • 由于逻辑上的“当且仅当”关系具有传递性（如果 A $\iff$ B 且 B $\iff$ C，则 A $\iff$ C），我们可以得出结论：对于所有 $z$，$xz \in L \iff wz \in L$。
   • 这正是 $x \sim_L w$ 的定义。
   • 所以，$\sim_L$ 满足传递性。
4. 结论:
   • 因为 $\sim_L$ 同时满足自反、对称和传递三个性质，所以它是一个等价关系。

这段话的作用是复习一个数学概念：等价关系如何引出等价类和划分。

1. “等价关系 $\sim$ 会导出等价类”
   • 一旦我们有了一个等价关系 $\sim$（比如上一节的 $\sim_L$），我们就可以定义等价类。
   • 对于任何一个元素 $x$，它的等价类（通常记作 $[x]$）是集合中所有与 $x$ 等价的元素的集合。
   • 形式化地：$[x] = \{ y \in S \mid x \sim y \}$。
2. “这些等价类将 $S$ 划分为...”
   • 划分 (Partition) 是一个非常重要的概念。一个集合 $S$ 的划分是指把 $S$ 分成若干个非空子集 $S_1, S_2, \ldots$，这些子集满足两个条件：
   • 并集为全集: $S_1 \cup S_2 \cup \ldots = S$ (所有子集合并起来等于原集合，没有遗漏任何元素)。
   • 两两不相交: 对于任何 $i \neq j$，$S_i \cap S_j = \emptyset$ (任意两个不同的子集都没有共同元素)。
   • 等价类正好构成了对原集合的一个划分。每个元素都属于且仅属于一个等价类。
3. 例子：模3同余
   • 集合: $S = \mathbb{Z}$ (所有整数)。
   • 等价关系: $a \sim b$ 当且仅当 $a$ 和 $b$ 除以 3 的余数相同。这记作 $a \equiv b \pmod 3$。这是一个标准的等价关系。
   • 划分/等价类:
   • [0]: 所有除以3余0的整数。$[0] = \{\ldots, -6, -3, 0, 3, 6, \ldots\}$。
   • [1]: 所有除以3余1的整数。$[1] = \{\ldots, -5, -2, 1, 4, 7, \ldots\}$。
   • [2]: 所有除以3余2的整数。$[2] = \{\ldots, -4, -1, 2, 5, 8, \ldots\}$。
   • 这三个等价类 $[0], [1], [2]$ 就构成了对整数集 $\mathbb{Z}$ 的一个划分。
   • 任何一个整数都必然属于这三类中的一类。
   • 不可能有一个整数同时属于两类。
   • 在这个例子中，等价类的数量是 3，是有限的。

这是一个非常重要但又很简单的观察。

1. “如果 $x \in L$ 且 $y \notin L$”
   • 我们取了两个字符串 $x$ 和 $y$。它们自身的“命运”就已经不同了：一个本身就在语言 $L$ 中，另一个不在。
2. “那么 $x$ 和 $y$ 对于 $L$ 是可区分的”
   • 为什么？因为我们可以找到一个区别扩展。
3. “我们可以取区别扩展为空字符串 $\epsilon$。”
   • 让我们来验证一下 $z = \epsilon$ 是否是区别扩展。
   • 考虑 $xz = x\epsilon = x$。我们已知 $x \in L$。
   • 考虑 $yz = y\epsilon = y$。我们已知 $y \notin L$。
   • 一个在 $L$ 中，一个不在 $L$ 中。这完全符合区别扩展的定义。
   • 所以，$x$ 和 $y$ 确实是可区分的。
4. “因此，每个等价类包含的字符串要么全部在 $L$ 中，要么全部不在 $L$ 中。”
   • 这是上面结论的直接推论。
   • 回想一下，一个等价类是由相互不可区分的字符串组成的。
   • 如果一个等价类里，既有在 $L$ 中的字符串 $x$，又有不在 $L$ 中的字符串 $y$，那么根据我们刚刚的证明，$x$ 和 $y$ 将是可区分的。
   • 这与“它们在同一个等价类中”这个前提相矛盾。
   • 因此，这种情况不可能发生。
   • 唯一可能的情况是：一个等价类里的所有字符串，要么都在 $L$ 里，要么都不在 $L$ 里。我们称这样的等价类是“纯洁的”。

这是整篇讲义的核心，是前述所有铺垫的最终集结。我们将它分解成三个部分来理解。

第一部分：正则性的特征刻画

• “$L$ 是正则的当且仅当 $\sim_{L}$ 的等价类数量是有限的。”
• “当且仅当” (if and only if, iff): 这是一个双向箭头，意味着两边的陈述是完全等价的。
• 方向一 (=>): 如果 $L$ 是正则的，那么 $\sim_L$ 的等价类数量一定是有限的。
• 直觉：既然 $L$ 可以被一个状态有限的 DFA 识别，而 DFA 的状态本质上就是对字符串进行分类，那么这种分类的数量（即等价类的数量）也必然是有限的。
• 方向二 (<=): 如果 $\sim_L$ 的等价类数量是有限的，那么 $L$ 一定是正则的。
• 直觉：如果所有字符串可以被归结为有限多种“本质不同的类别”（等价类），我们就可以构造一个 DFA，让它的每一个状态正好对应一个等价类。因为等价类数量有限，所以这个 DFA 的状态数也是有限的，因此 $L$ 是正则的。

第二部分：最小状态数的确定

• “此外，如果 $L$ 是正则的，那么 $\sim_{L}$ 的等价类数量也是识别 $L$ 的最小 DFA 的状态数。”
• 这部分给出了一个惊人的精确结论。它不仅说等价类数量是有限的，还说这个数量不多不少，正好等于识别 $L$ 所需的最小状态数。
• 令 $k$ 为 $\sim_L$ 的等价类数量。
• 定理说：识别 $L$ 的最小 DFA 的状态数 = $k$。
• 这意味着什么？
• 下界: 我们不能用少于 $k$ 个状态来识别 $L$。为什么？因为 $k$ 个等价类中的每一个都与其他等价类中的字符串可区分。我们可以从每个等价类中取出一个代表字符串，形成一个大小为 $k$ 的两两可区分集。根据引理 2.2，DFA 至少需要 $k$ 个状态。
• 上界: 我们可以构造出一个正好有 $k$ 个状态的 DFA 来识别 $L$。证明部分将会展示这个构造过程。

整合理解:

Myhill-Nerode 定理完美地连接了三个概念：

1. 语言的正则性 (一个抽象属性)
2. 不可区分关系 $\sim_L$ 的等价类数量 (一个组合数学属性)
3. 最小 DFA 的状态数 (一个计算模型复杂度属性)

定理说，这三者是紧密锁定的。语言是正则的 $\iff$ 等价类数量有限 $\iff$ 存在一个最小 DFA。并且，等价类的数量 == 最小 DFA 的状态数。

这部分将定理的证明分解为三个逻辑步骤。前两步证明了定理的“当且仅当”部分，第三步证明了“最小状态数”部分。

1. 陈述 1 (正则 $\implies$ 有限等价类): 这是证明定理的 "=>" 方向。假设我们已经有了一个能识别 $L$ 的 DFA（因为 $L$ 是正则的），我们要说明等价类的数量不可能是无限的。
2. 陈述 2 (有限等价类 $\implies$ 正则): 这是证明定理的 "<=" 方向。假设我们知道等价类数量是有限的，我们要说明 $L$ 必须是正则的。证明的方法是构造性的：我们直接用这些等价类作为蓝图，来建造一个能识别 $L$ 的 DFA。
3. 陈述 3 (等价类数量 = 最小状态数): 这部分是锦上添花，但也是定理的精髓。它利用了前两步的结论。
   • 证明分为两半：
   • (下界) 最小状态数 $\ge$ 等价类数量: 这在引理 2.2 已经暗示了。从每个等价类挑一个代表，它们两两可区分，所以DFA 至少需要那么多状态。
   • (上界) 最小状态数 $\le$ 等价类数量: 陈述 2 的构造过程给出了一个状态数恰好等于等价类数量的 DFA。既然存在这样一个 DFA，那么最小的那个 DFA 的状态数肯定不会超过这个数量。
   • 结合上下界，就证明了两者相等。

这部分的证明非常巧妙，它没有直接证明“$L$ 是正则的 $\implies$ 等价类有限”，而是证明了其逆否命题 (Contrapositive)。

• 原命题: $P \implies Q$ (如果P成立，那么Q成立)
• 逆否命题: $\neg Q \implies \neg P$ (如果Q不成立，那么P不成立)
• 在逻辑上，原命题和其逆否命题是完全等价的。证明了逆否命题，就等于证明了原命题。

在这里：

• $P$: $L$ 是正则的。
• $Q$: $\sim_L$ 的等价类数量是有限的。
• $\neg P$: $L$ 不是正则的。
• $\neg Q$: $\sim_L$ 的等价类数量是无限的。
• 要证明的逆否命题是: 如果 $\sim_L$ 的等价类数量是无限的，那么 $L$ 不是正则的。

证明步骤:

1. “假设 $\sim_{L}$ 有无限个等价类。”
   • 这是逆否命题的起点。
2. “这意味着存在一个包含无限个字符串的集合...使得其中每两个字符串...是可区分的。”
   • 如果有无限个等价类，我们可以从每个等价类中挑选一个代表字符串。由于不同等价类中的字符串必然是可区分的，这样我们就得到了一个无限的、两两可区分的字符串集合。
3. “现在根据引理 2.2...”
   • 引理 2.2 说，如果有一个大小为 $k$ 的两两可区分集，那么 DFA 至少需要 $k$ 个状态。
   • 现在我们有一个无限的两两可区分集。
4. “对于我们选取的任何数量 $k$，都不可能存在具有 $k$ 个状态且识别 $L$ 的 DFA。”
   • 我们可以从这个无限集合中，轻松取出 $k+1$ 个字符串。这 $k+1$ 个字符串构成了一个大小为 $k+1$ 的两两可区分集。
   • 根据引理 2.2，任何识别 $L$ 的 DFA 都至少需要 $k+1$ 个状态。
   • 所以，一个只有 $k$ 个状态的 DFA 绝对不可能识别 $L$。
   • 这里的 $k$ 是任意一个正整数。
5. “因此，不存在识别 $L$ 的 DFA（具有任何有限数量的状态）”
   • 既然对于任何有限数 $k$，一个 $k$ 状态的 DFA 都不够用，那就意味着没有任何一个具有有限状态的 DFA 能够识别 $L$。
6. “这意味着 $L$ 不是正则的。”
   • 根据正则语言的定义（一个语言是正则的，当且仅当存在一个有限自动机识别它），如果不存在任何有限状态的 DFA，那么 $L$ 就不是正则的。
   • 证明完成。我们成功证明了逆否命题，因此原命题也成立。

这是一个构造性证明 (Constructive Proof)。它通过直接搭建一个满足条件的 DFA 来证明 $L$ 的正则性。

构造蓝图:

• 核心思想: 让 DFA 的状态直接与 $\sim_L$ 的等价类一一对应。
• 前提: 我们假设等价类的数量是有限的，比如有 $k$ 个。

第一步：重要的观察 (为转移函数的良定义性铺路)

• 观察: 如果 $x$ 和 $y$ 在同一个等价类中 (即 $x \sim_L y$)，那么把它们分别加上同一个后缀 $w$ 之后，得到的新字符串 $xw$ 和 $yw$ 也必然在同一个等价类中 (即 $xw \sim_L yw$)。
• 证明: $x \sim_L y$ 意味着对任意的 $z'$, $xz' \in L \iff yz' \in L$。
• 我们想证明 $xw \sim_L yw$。这需要证明对任意的 $u$, $xwu \in L \iff ywu \in L$。
• 我们可以令 $z' = wu$。由于 $z'$ 也是一个合法的字符串，根据 $x \sim_L y$ 的前提，我们有 $x(wu) \in L \iff y(wu) \in L$。
• 这正是我们要证明的。所以这个观察成立。
• 意义: 这个观察保证了等价类的演化是“一致的”。从一个等价类中的任何字符串出发，经过相同的输入，都会到达同一个目标等价类。这对于定义一个“确定性”的转移至关重要。

第二步：构造 DFA M = ($Q, \Sigma, \delta, q_0, F$)

这是 DFA 的五元组定义。

• $Q$ (状态集):
• 集合 $Q$ 就是所有 $\sim_L$ 等价类的集合。
• 因为我们假设等价类数量有限，所以 $Q$ 是一个有限集，满足 DFA 的要求。
• $\Sigma$ (字母表):
• 就是语言 $L$ 的字母表。
• $q_0$ (起始状态):
• 我们需要一个状态作为起点。最自然的选择是代表“什么都还没读”的那个等价类。
• “什么都还没读”就是空字符串 $\epsilon$。
• 所以，起始状态就是等价类 $[\epsilon]$。
• $F$ (接受状态集):
• 哪些状态（等价类）应该是接受状态？
• 根据备注 2.4，一个等价类要么全在 $L$ 中，要么全不在 $L$ 中。
• 所以，我们把那些“全在 $L$ 中”的等价类定义为接受状态。
• 形式化地，$F = \{ [x] \in Q \mid x \in L \}$。这个定义是有效的，因为如果 $[x]$ 在 $F$ 中，对于 $[x]$ 中的任何其他成员 $y$，由于 $x \sim_L y$，且 $x\in L$，我们不能有 $y \notin L$ (否则 $z=\epsilon$ 会区分它们)。所以 $y$ 也必须在 $L$ 中。
• $\delta$ (转移函数):
• 这是最关键的部分。$\delta$ 的功能是：给定一个当前状态（一个等价类 $[x]$）和一个输入字符 $a$，它应该转移到哪个新状态？
• 定义: $\delta([x], a) = [xa]$。
• 解释: 如果机器当前在代表了所有与 $x$ 不可区分的字符串的状态 $[x]$，在读入一个字符 $a$ 之后，它会进入一个新的状态，这个状态代表了所有与 $xa$ 不可区分的字符串。
• 良定义性 (Well-definedness): 这个定义有没有问题？状态是等价类，但我们是用等价类中的一个代表元素 $x$ 来定义转移的。如果我用同一个等价类的另一个代表 $x'$ 来定义，结果会一样吗？
• 假设 $[x] = [x']$，即 $x \sim_L x'$。
• 我们需要验证 $\delta([x], a)$ 是否等于 $\delta([x'], a)$。
• $\delta([x], a) = [xa]$
• $\delta([x'], a) = [x'a]$
• 我们需要验证 $[xa]$ 是否等于 $[x'a]$，即 $xa \sim_L x'a$。
• 这正是我们在“第一步：重要的观察”中证明的结论（令 $w=a$）。
• 因此，转移函数的定义是“良定义的”，它不依赖于我们选择哪个代表元素，结果都是唯一的。

第三步：证明构造的 DFA 识别 L

• 我们需要证明，对于任何字符串 $w$，将 $w$ 输入我们构造的 DFA $M$，当且仅当 $w \in L$ 时，$M$ 停在接受状态。
• 令 $w = a_1 a_2 \ldots a_n$。
• DFA 的计算过程:
• 从 $q_0 = [\epsilon]$ 开始。
• 读 $a_1$: 转移到 $\delta([\epsilon], a_1) = [\epsilon a_1] = [a_1]$。
• 读 $a_2$: 转移到 $\delta([a_1], a_2) = [a_1 a_2]$。
• ...
• 读 $a_n$: 转移到 $\delta([a_1\ldots a_{n-1}], a_n) = [a_1\ldots a_n]$。
• 最终状态: 读完整个字符串 $w$ 后，DFA 停在状态 $[w]$。
• 接受条件: 根据我们对 $F$ 的定义，状态 $[w]$ 是接受状态当且仅当 $w \in L$。
• 结论: 这个 DFA $M$ 准确地识别了语言 $L$。因为我们成功构造了一个有限状态的 DFA，$L$ 根据定义是正则的。

这部分证明非常简洁，因为它综合了前面的所有成果。它通过“夹逼”的方式证明等式。

1. 证明：最小状态数 $\le$ 等价类数量
   • 在“证明 2”中，我们构造了一个 DFA，我们称之为 $M_{MN}$ (Myhill-Nerode automaton)。
   • 这个 $M_{MN}$ 的状态数恰好等于 $\sim_L$ 的等价类数量。
   • 既然存在一个能够识别 $L$ 的 DFA，它的状态数是 $|Q_{M_{MN}}| = (\text{等价类数量})$，那么，所有能识别 $L$ 的 DFA 中，那个状态最少的（即最小 DFA），其状态数肯定不会超过这个值。
   • 所以，$(\text{最小状态数}) \le (\text{等价类数量})$。
2. 证明：最小状态数 $\ge$ 等价类数量
   • 令 $k$ 为 $\sim_L$ 的等价类数量。
   • 我们可以从这 $k$ 个不同的等价类中，每个取出一个代表字符串，形成一个集合 $S = \{x_1, x_2, \ldots, x_k\}$。
   • 因为这些字符串来自不同的等价类，所以它们两两可区分。
   • 我们得到了一个大小为 $k$ 的两两可区分集。
   • 根据引理 2.2，任何识别 $L$ 的 DFA 的状态数必须至少为 $k$。
   • 这当然也包括最小 DFA。
   • 所以，$(\text{最小状态数}) \ge k = (\text{等价类数量})$。
3. 结论
   • 我们已经证明了：
   • $(\text{最小状态数}) \le (\text{等价类数量})$
   • $(\text{最小状态数}) \ge (\text{等价类数量})$
   • 唯一能同时满足这两个不等式的情况就是相等。
   • 因此，$(\text{最小状态数}) = (\text{等价类数量})$。
4. 补充结论
   • “因此，上面构造的 DFA 是 L 的最小 DFA。”
   • 我们构造的 $M_{MN}$ 的状态数等于等价类数量。
   • 我们又证明了最小 DFA 的状态数也等于等价类数量。
   • 所以，我们构造的 $M_{MN}$ 的状态数就是最小状态数。
   • 在自动机理论中，可以进一步证明，任何具有最小状态数的 DFA 在结构上都是唯一的（同构的）。这意味着我们构造的 $M_{MN}$ 不仅状态数最小，它本质上就是那个唯一的最小 DFA。

这部分总结了 Myhill-Nerode 定理的两个主要应用方向。

应用一：分析和优化正则语言

1. “将语言分解为最基本的片段，即等价类”:
   • Myhill-Nerode 定理提供了一个独特的视角，让我们不从字符串本身，而是从“等价类”这个更高层次的抽象来理解语言。等价类是语言的“基因”或“原子成分”。
2. “这些等价类对应于该语言的最小 DFA”:
   • 等价类和最小 DFA 的状态之间存在一一对应的关系。这意味着，通过分析等价类，我们就能洞察最小 DFA 的结构和复杂性。
3. DFA 最小化算法的核心:
   • 虽然讲义不详细介绍，但它指明了方向。一个普通的、可能有冗余的 DFA 是怎么最小化的？
   • “所有最终处于同一状态的字符串必须属于同一个等价类”: 这是证明1的推论。一个状态内的字符串，它们的未来命运被绑定了，所以它们必须不可区分。
   • “最终处于两个不同状态的字符串可能仍然属于同一个等价类”: 这是DFA 存在冗余的关键！一个非最小的 DFA 可能用了两个或多个状态去做了本该一个状态就能做的事情。比如，状态 $q_1$ 和 $q_2$ 是不同的，但所有能到达 $q_1$ 的字符串，和所有能到达 $q_2$ 的字符串，它们其实都属于同一个大的等价类。
   • “这两个状态被称为是等价的，并且可以...合并为一个状态”: 这就是最小化算法的核心操作。算法会去寻找并合并这些“等价的状态”，直到每个状态都恰好对应一个 Myhill-Nerode 等价类，此时 DFA 就最小化了。

应用二：证明语言非正则

1. “证明等价类的数量是无限的”:
   • 根据定理的“当且仅当”部分，语言非正则 $\iff$ 等价类数量无限。
   • 所以，证明非正则性的任务，就转化为了证明等价类数量是无限的。
2. “这可以通过找出无限多个字符串，使得其中没有两个是等价的...来实现”:
   • 这是证明等价类数量无限的具体操作方法。
   • 我们只需要构造一个无限的字符串集合 $S = \{s_1, s_2, s_3, \ldots\}$。
   • 并且证明，对于这个集合里任意两个不同的成员 $s_i$ 和 $s_j$，它们都是可区分的 ($s_i \not\sim_L s_j$)。
   • 如果能做到这一点，就说明每个 $s_i$ 都必须属于一个独一无二的等价类。
   • 既然有无限个这样的 $s_i$，那就必须有无限个等价类。
   • 任务完成，语言被证明为非正则。这比泵引理更直接，有时也更简单。

这个例子分析一个简单的正则语言 $L = \{0, 01, 011, 0111, \ldots\}$，并找出它的等价类。

第一步：识别不同的“命运”类别

我们要思考，一个字符串在被处理的过程中，有哪些“本质不同”的状态？

1. 刚开始，什么都没读: 这是字符串 $\epsilon$。它的未来是充满希望的，如果接下来读到一个 '0'，就走上了通往成功的正确道路。
2. 走在正确的路上: 已经读了一个 '0'，或者 '0' 后面跟了一些 '1'。比如 "0", "01", "011"。这些字符串本身就在语言 $L$ 中。它们接下来的命运是什么？如果再读一个 '1'，它们依然在正确的路上。如果读一个 '0'，就失败了。
3. 已经走错了路，万劫不复: 字符串的格式已经错了，比如以 '1' 开头 ("1", "10")，或者包含了多个 '0' ("00", "010")。一旦到了这个地步，无论后面再追加什么字符串 $z$，最终结果都不可能再属于 $L$ 了。这是一个“死亡”状态。

第二步：将这些类别形式化为等价类

• 等价类 1: $[\epsilon]$ (初始状态)
• 这个类只包含空字符串 $\epsilon$。
• 为什么它自成一类？因为它和任何非空字符串 $w$ 都是可区分的。
• 证明: 取 $z=0$。$ \epsilon z = 0 \in L$。但对于任何非空 $w$，如果 $w$ 以0开头，则 $w0$ 含有两个0，不在L中；如果$w$以1开头，则$w0$以1开头，不在L中。所以 $w0 \notin L$。因此 $\epsilon$ 和任何非空 $w$ 可区分。

• 等价类 2: $[1]$ (死亡状态/垃圾桶状态)
• 这个类包含所有“格式错误”的字符串。
• 比如：以 '1' 开头的字符串 ("1", "10", "11", ...)，包含多于一个 '0' 的字符串 ("00", "010", "001", ...)，在 '0' 之前有 '1' 的字符串（这是以1开头的情况）。
• 为什么它们都属于一个等价类？因为它们都不可区分。
• 证明: 设 $x, y$ 都是格式错误的字符串。对于任何后缀 $z$，$xz$ 和 $yz$ 的格式也一定是错误的（比如 $x$ 有两个0，那么 $xz$ 至少有两个0），所以 $xz \notin L$ 且 $yz \notin L$。它们的命运完全相同（永远被拒绝）。因此它们不可区分。我们用 "1" 作为这个等价类的代表，记作 $[1]$（也可以用 "00" 等）。

• 等价类 3: $[0]$ (接受状态)
• 这个类包含所有在语言 $L$ 中的字符串。即 $L$ 本身: $\{0, 01, 011, \ldots\}$。
• 为什么它们都属于同一个等价类？
• 证明: 设 $x, y$ 都是 $L$ 中的字符串（比如 $x=01^i, y=01^j$）。对于任何后缀 $z$：
• 如果 $z$ 的形式是 $1^k$ (任意数量的1)，那么 $xz = 01^{i+k}$ 也在 $L$ 中，$yz = 01^{j+k}$ 也在 $L$ 中。命运相同。
• 如果 $z$ 包含 '0' 或者不是全由 '1' 组成，那么 $xz$ 和 $yz$ 都会包含第二个 '0' 或其他非法字符，导致它们都不在 $L$ 中。命运也相同。
• 因此，任何两个 $L$ 中的字符串都是不可区分的。它们构成一个等价类。我们用 "0" 作为代表，记作 $[0]$。

第三步：应用 Myhill-Nerode 定理

• 我们找到了 3 个等价类: $[\epsilon]$, $[1]$, $[0]$。
• 等价类的数量是 3，是有限的。
• 结论:

1. 语言 $L$ 是正则的。
2. 识别 $L$ 的最小 DFA 恰好有 3 个状态。这三个状态就分别对应这三个等价类。

这部分通过展示一个具体的 DFA 来验证我们之前的等价类分析。

• DFA 状态与等价类的对应:
• 初始状态 (unnamed): 这个状态只在开始时处于，没有任何箭头指向它。这完美对应了等价类 $[\epsilon]$，它只包含空字符串。当读入 '0'，离开此状态；读入 '1'，也离开此状态。之后再也回不来。
• 状态 $q_1$ (接受状态):
• 如何到达？从初始状态读 '0'。所以字符串 "0" 到达 $q_1$。
• 在 $q_1$ 时读 '1'，会回到 $q_1$。所以 "01", "011", ... 都停在 $q_1$。
• 所有停在 $q_1$ 的字符串，恰好就是语言 $L$ 中的所有字符串。
• 这完美对应了等价类 $[0]$。
• 状态 $q_{bad}$ (垃圾桶状态):
• 如何到达？从初始状态读 '1'；或从 $q_1$ 读 '0'；或在 $q_{bad}$ 时读任何字符。
• 这包括了所有以 '1' 开头的字符串，以及所有包含多个 '0' 的字符串。
• 一旦进入 $q_{bad}$，就永远出不去了。
• 这完美对应了“格式错误”的等价类 $[1]$。

• “$L$ 本身完全包含在一个等价类中，这一事实对应于最小 DFA 只有一个接受状态这一事实”:
• 这是一个有趣的观察。因为所有 $L$ 中的字符串都是不可区分的，它们形成了一个大的等价类。所以在最小 DFA 中，它们都必须被映射到同一个状态。由于它们是接受字符串，这个状态必须是接受状态。如果最小 DFA 有两个或多个接受状态 $q_A, q_B$，那么到达 $q_A$ 的字符串和到达 $q_B$ 的字符串就必然是可区分的，从而它们属于不同的等价类。反之，如果所有 $L$ 里的字符串都属于同一个等价类，那么在最小 DFA 里它们只能对应一个状态，因此只有一个接受状态。

这个例子非常经典，它展示了 DFA 和 NFA 之间著名的指数级差距，并用 Myhill-Nerode 定理给出了 DFA 状态数的精确证明。

语言 $L_n$ 的直觉:

• 这个语言关心的是“倒数第 $n$ 位”。为了判断一个字符串 $w$ 是否在 $L_n$ 中，你至少需要看到 $n$ 个字符。当你读完整个字符串后，你需要“记住”最后 $n$ 个字符是什么，才能做出判断。
• 这暗示了 DFA 的状态必须编码关于“最近 $n$ 个字符”的信息。

证明部分一：证明至少有 $2^n$ 个等价类

1. 目标: 找到一个大小为 $2^n$ 的两两可区分集。
2. 候选集合: 最自然的候选者是所有长度为 $n$ 的二进制字符串。这个集合正好有 $2^n$ 个成员。例如，当 $n=3$ 时，集合是 $\{000, 001, 010, 011, 100, 101, 110, 111\}$。
3. 证明两两可区分:
   • 任取其中两个不同的字符串，记作 $w=w_1 w_2 \ldots w_n$ 和 $w'=w'_1 w'_2 \ldots w'_n$。
   • 因为 $w \neq w'$，它们至少在某一位 $i$ 上不同。即 $w_i \neq w'_i$。
   • 如何构造区别扩展 $z$？: 我们的目标是把这个不同的第 $i$ 位“推到”倒数第 $n$ 位去。
   • 当前 $w_i$ 是 $w$ 的第 $i$ 位。在它后面追加一个长度为 $i-1$ 的字符串 $z$，那么 $w_i$ 就变成了新字符串 $wz$ 的第 $i$ 位，同时也是倒数第 $(n-i)+(i-1)+1 = n$ 位！
   • 选择 $z$: 我们选择 $z = 0^{i-1}$ ( $i-1$ 个0)。
   • 验证:
   • 考虑 $wz = w_1 \ldots w_i \ldots w_n 0^{i-1}$。它的总长度是 $n + (i-1)$。它的倒数第 $n$ 位是哪个字符？从后往前数，先跳过 $i-1$ 个0，再跳过 $w_n, w_{n-1}, \ldots, w_{i+1}$ (共 $n-i$ 个字符)，下一个就是 $w_i$。所以 $wz$ 的倒数第 $n$ 位是 $w_i$。
   • 同理，$w'z$ 的倒数第 $n$ 位是 $w'_i$。
   • 结论: 因为 $w_i \neq w'_i$，所以一个为 '1'，一个为 '0'。这意味着 $wz$ 和 $w'z$ 中，一个在 $L_n$ 中，另一个不在。
   • 因此，$w$ 和 $w'$ 是可区分的。
4. 小结: 由于所有 $2^n$ 个长度为 $n$ 的字符串两两可区分，它们必须分属于 $2^n$ 个不同的等价类。所以，等价类的数量至少是 $2^n$。根据 Myhill-Nerode 定理，最小 DFA 的状态数至少是 $2^n$。

证明部分二：证明恰好有 $2^n$ 个等价类

1. 目标: 证明任何字符串都与某个长度为 $n$ 的字符串不可区分。如果能证明这一点，就说明所有的字符串都可以被归入由长度为 $n$ 的字符串所代表的这 $2^n$ 个等价类中，不存在更多的等价类了。
2. 直觉: 要判断一个长字符串 $wz$ 是否在 $L_n$ 中，重要的是 $wz$ 的最后 $n$ 个字符。而 $wz$ 的最后 $n$ 个字符，只取决于 $z$ 以及 $w$ 的最后若干个字符。更准确地说，对于任何字符串 $x$，它的“未来命运”完全由它的长度为n的后缀所决定。
3. 形式化论证:
   • 情况 1: $|w| > n$:
   • 设 $w$ 的长度为 $n$ 的后缀是 $s$。即 $w=us$ 且 $|s|=n$。我们声称 $w \sim_{L_n} s$。
   • 为什么？对于任何后缀 $z$，我们要比较 $wz$ 和 $sz$。
   • $wz$ 是否在 $L_n$ 中，取决于 $wz$ 的最后 $n$ 个字符。这 $n$ 个字符完全由 $s$ 和 $z$ 决定。
   • $sz$ 是否在 $L_n$ 中，也取决于 $sz$ 的最后 $n$ 个字符。
   • $wz$ 和 $sz$ 的最后 $n$ 个字符是完全一样的！(因为 $w$ 中 $s$ 前面的 $u$ 部分已经被“挤掉”了，不影响最后 $n$ 位)。
   • 所以，$wz \in L_n \iff sz \in L_n$。它们不可区分。
   • 情况 2: $|w| < n$:
   • 设 $w'$ 是在 $w$ 前面补上 $n-|w|$ 个 '0' 得到的字符串，即 $w' = 0^{n-|w|}w$。$|w'|=n$。我们声称 $w \sim_{L_n} w'$。
   • 为什么？对于任何后缀 $z$，$wz$ 和 $w'z$ 的命运取决于它们各自的倒数第 $n$ 位。而这两个位置的字符是相同的（都来自于 $w$ 或者补上的 '0'）。
4. 结论: 任何字符串都与一个长度为 $n$ 的字符串等价。这意味着所有的等价类都可以由长度为 $n$ 的 $2^n$ 个字符串来代表。因此，等价类的数量恰好是 $2^n$。

最终结论:

• $L_n$ 的等价类数量是 $2^n$。
• 因为这个数是有限的，所以 $L_n$ 是正则的。
• 识别 $L_n$ 的最小 DFA 恰好有 $2^n$ 个状态。每个状态对应一个可能的长度为 $n$ 的后缀。

与 NFA 的对比:

• 识别 $L_n$ 的 NFA 可以非常简单。它“猜测”哪一位是倒数第 $n$ 位。
• NFA 构造:
• 一个初始状态 $q_0$。
• 在 $q_0$ 看到 '1' 时，可以非确定性地跳转到一个特殊的状态 $q_1$（这代表“我猜这个1是倒数第n位”），也可以留在 $q_0$。看到 '0' 只能留在 $q_0$。
• 从 $q_1$ 开始，需要再读 $n-1$ 个字符。我们用 $n-1$ 个状态 $q_2, \ldots, q_n$ 来“数”这 $n-1$ 步。
• $q_n$ 是唯一的接受状态。
• 总状态数是 $q_0, q_1, \ldots, q_n$，共 $n+1$ 个。
• 对比: DFA 需要 $2^n$ 个状态，而 NFA 只需要 $n+1$ 个。当 $n$ 很大时，这个差距是巨大的。这说明了 NFA 在某些问题上的简洁表达能力。

这部分引出了 Myhill-Nerode 定理的第二个主要用途：证明语言的非正则性。它预告了将要用新方法解决老问题，并暗示了这个新方法的威力可能比泵引理更强。

证明非正则的策略回顾:

• 根据 Myhill-Nerode 定理，语言非正则 $\iff$ 等价类数量无限。
• 我们的任务就是去证明等价类数量是无限的。
• 具体方法: 构造一个无限的字符串集合 $S = \{s_1, s_2, s_3, \ldots\}$，并证明集合中任意两个不同的元素 $s_i, s_j$ 都是可区分的。

1. 语言: $L$ 是所有 0 和 1 数量相等的字符串的集合。例如, $\epsilon, 01, 10, 0011, 0101$ 都在 $L$ 中。
2. 目标: 证明 $L$ 非正则。
3. 策略: 找一个无限的、两两可区分的集合。
4. 候选集合: 一个简单的无限集合是 $S = \{ \epsilon, 0, 00, 000, \ldots, 0^k, \ldots \}$。
5. 证明两两可区分:
   • 从 $S$ 中任取两个不同的字符串，令它们为 $x=0^k$ 和 $y=0^j$，其中 $k \neq j$ (假设 $k,j \ge 0$)。
   • 我们需要找一个区别扩展 $z$。
   • 直觉: $x$ "欠"了 $k$ 个 '1' 才能达到平衡。$y$ "欠"了 $j$ 个 '1'。我们可以通过添加适量的 '1' 来“帮助”其中一个达到平衡，而另一个则不能。
   • 选择 $z$: 我们选择 $z=1^k$。这个 $z$ 是为 $x$ "量身定做"的。
   • 验证:
   • 考虑 $xz = 0^k 1^k$。这里 '0' 的数量是 $k$，'1' 的数量也是 $k$。它们相等。所以 $xz \in L$。
   • 考虑 $yz = 0^j 1^k$。这里 '0' 的数量是 $j$，'1' 的数量是 $k$。因为 $j \neq k$，所以 '0' 和 '1' 的数量不相等。所以 $yz \notin L$。
   • 结论: $xz$ 和 $yz$ 的命运不同。因此，$x=0^k$ 和 $y=0^j$ 是可区分的。
6. 最终论证:
   • 我们已经证明，对于集合 $S=\{0^k \mid k \ge 0\}$ 中的任意两个不同元素，它们都是可区分的。
   • 这意味着它们必须属于不同的等价类。
   • 由于集合 $S$ 是无限的，所以必然存在无限多个等价类。
   • 根据 Myhill-Nerode 定理，如果等价类数量是无限的，那么语言 $L$ 就不是正则的。

1. 语言: $L$ 是所有回文串的集合。回文串是指正读和反读都一样的字符串，例如 $\epsilon, a, b, aa, bb, aba, bab, abba$。
2. 目标: 证明 $L$ 非正则。
3. 策略: 找一个无限的、两两可区分的集合。
4. 候选集合: 同样，一个简单的无限集合是 $S = \{ \epsilon, a, aa, aaa, \ldots, a^k, \ldots \}$。
5. 证明两两可区分:
   • 从 $S$ 中任取两个不同的字符串，令它们为 $x=a^k$ 和 $y=a^j$，其中 $k \neq j$ (假设 $k,j \ge 0$)。
   • 我们需要找一个区别扩展 $z$。
   • 直觉: $x=a^k$ 是一个前缀。要使整个字符串成为回文，后缀必须是 $x$ 的“镜像”。我们可以构造一个后缀，它正好是 $x$ 的镜像，但不是 $y$ 的镜像。
   • 选择 $z$: 我们选择 $z = b a^k$。这里 'b' 是一个“分隔符”，后面跟着 $x$ 本身。
   • 验证:
   • 考虑 $xz = a^k b a^k$。这个字符串以 $b$ 为中心，左右两边都是 $a^k$，它是对称的，所以是一个回文串。因此 $xz \in L$。
   • 考虑 $yz = a^j b a^k$。这个字符串的左边是 $a^j$，右边是 $a^k$。因为 $j \neq k$，所以它不是对称的，不是回文串。因此 $yz \notin L$。
   • 结论: $xz$ 和 $yz$ 的命运不同。因此，$x=a^k$ 和 $y=a^j$ 是可区分的。
6. 最终论证:
   • 我们已经证明，对于集合 $S=\{a^k \mid k \ge 0\}$ 中的任意两个不同元素，它们都是可区分的。
   • 这意味着它们必须属于不同的等价类。
   • 由于集合 $S$ 是无限的，所以必然存在无限多个等价类。
   • 根据 Myhill-Nerode 定理，语言 $L$ 不是正则的。

• 其他候选集: 我们可以选择 $S' = \{a, ab, abb, abbb, \ldots, ab^k, \ldots\}$。对于 $x=ab^k, y=ab^j$ ($k \neq j$)，选择 $z = (ab^k)^R = b^k a$ 作为区别扩展。$xz$ 是回文，$yz$ 不是。
• “每个字符串都在它自己的等价类中”: 这个论断更强。它意味着对于任意两个不同的字符串 $x, y$，它们都是可区分的。证明起来可能更复杂，但直觉上是对的，因为要形成回文，需要的“镜像”后缀是完全由前缀决定的，不同的前缀需要不同的镜像。
• “但我们上面的证明更简单”: 这是一个重要的解题策略思想。我们不需要把所有等价类都找出来。为了证明非正则，我们只需要找到一个无限的、两两可区分的子集就足够了。选择最简单的那个子集（比如 $a^k$）来论证，可以大大简化证明过程。