Myhill–Nerode 定理 | Codeboy's Blog

形式陈述

给定语言 $L\subseteq\Sigma^*$ ，在所有字上定义 Nerode 关系

x\equiv_L y \quad\Longleftrightarrow\quad \forall z\in\Sigma^*,\;xz\in L\iff yz\in L.

它是等价关系，并且对右拼接稳定：若 $x\equiv_Ly$ ，则对任意 $w$ 都有 $xw\equiv_Lyw$ 。等价地，定义语言对前缀 $x$ 的左商（也称前缀残余）

x^{-1}L=\{z\in\Sigma^*:xz\in L\},

就有 $x\equiv_Ly$ 当且仅当 $x^{-1}L=y^{-1}L$ 。

Myhill–Nerode 定理断言：

$L$ 是正则语言，当且仅当 $\equiv_L$ 的等价类个数有限；
若类数为 $k$ ，识别 $L$ 的最小 DFA 恰有 $k$ 个可达状态；
删除不可达状态后，最小 DFA 在保持初态、转移与接受状态的同构意义下唯一。

从 DFA 得到有限指标

设 DFA $M=(Q,\Sigma,\delta,q_0,F)$ 识别 $L$ 。若

\delta^*(q_0,x)=\delta^*(q_0,y),

那么从这个共同状态继续读取任意 $z$ 会到达同一终点，因此 $xz$ 与 $yz$ 必然同时接受或同时拒绝，即 $x\equiv_Ly$ 。于是每个可达 DFA 状态承载至多一种未来行为，而 Nerode 类数不超过可达状态数。特别地，任何识别 $L$ 的 DFA 至少需要与 Nerode 类一样多的状态。

注意逆命题对一台未最小化 DFA 未必成立：两个不同状态可能对所有后缀行为完全相同。机器可以人为复制状态，语言的 Nerode 关系不会因此产生新类。

从有限指标构造 DFA

反过来，若 $\equiv_L$ 只有有限多个类，就以这些类本身为状态：

Q_L=\Sigma^*/{\equiv_L},\qquad q_0=[\varepsilon],\qquad \delta_L([x],a)=[xa],

F_L=\{[x]:x\in L\}.

若 $[x]=[y]$ ，右不变性保证 $[xa]=[ya]$ ，所以转移不依赖代表元；在等价定义中取 $z=\varepsilon$ ，又可知一个类不会同时含有 $L$ 内外的字，所以 $F_L$ 也定义良好。对字长归纳得到

\delta_L^*([\varepsilon],x)=[x],

商自动机因而恰好识别 $L$ 。它每个 Nerode 类使用一个状态，达到前一方向给出的下界，所以最小。

任何可达最小 DFA 的状态都由某个前缀到达。把该状态映到这个前缀的 Nerode 类，映射保持初态、转移和接受性；若两个状态落在同一类，就可继续合并而不改变语言，与最小性矛盾。映射因此为双射，也证明最小 DFA 的唯一性。

直觉

读完前缀后，过去只通过一份“哪些后缀仍能成功”的未来清单影响判断，原来的字符序列已经无需保留。两个前缀若清单相同，任何识别器都没有理由继续区分它们；若清单不同，就存在一个具体后缀揭示差异，合并它们必定让至少一个完整字判断错误。

最小 DFA 的状态不是设计者凭经验挑出的标签，而是语言所有不同残余的规范名字。转移 $[x]\xrightarrow{a}[xa]$ 表示读一个符号会怎样更新未来清单，接受态则是包含空后缀的残余。定理由此直接从语言语义读出最低记忆量，无需先猜一台自动机再证明它最小。

“可区分”必须针对右侧续写：找到 $z$ 使 $xz\in L$ 而 $yz\notin L$ ，就证明 $x\not\equiv_Ly$ 。区分后缀可以依赖于所比较的一对前缀；不要求一条万能测试串同时区分所有状态。反过来，只试过若干短后缀而未发现差异，并不能证明等价。

含子串 ab 的语言对应的三状态最小 DFA，并标出区分三个 Nerode 类的后缀证书 — Nerode 三类与最小 DFA

例子与边界

令

L=\{w\in\{a,b\}^*:w\text{ 含子串 }ab\}.

前缀的未来行为恰分三类：尚未出现 ab 且末尾不是 a，可由 $\varepsilon$ 代表；尚未出现 ab 且末尾是 a，可由 a 代表；已经出现 ab，可由 ab 代表。第一、第二类由后缀 b 区分，因为 b 不含 ab 而 ab 含；第三类与前两类都可由空后缀区分，因为它已经接受。于是最小 DFA 恰有三个状态：无候选前缀、刚见到候选 a、已经匹配成功。

这份论证同时给了上界和下界。三类描述覆盖所有前缀，故商自动机至多三状态；三个代表两两可区分，故任何 DFA 至少三状态。只展示一台三状态 DFA 只能证明上界，若没有区分证书，不能排除还存在两状态实现。

考虑复制语言

C=\{x\#x:x\in\{0,1\}^*\}.

前缀集合 $\{x\#:x\in\{0,1\}^*\}$ 两两可区分：对不同的 $x,y$ ，接后缀 $x$ 后有 $x\#x\in C$ ，而 $y\#x\notin C$ 。因此 $C$ 有无限多个 Nerode 类，不是正则语言。这个证书准确指出有限状态缺失的信息：分隔符前的整段任意长文本必须留到后半段逐字核对。

关系是右同余，因为标准自动机从左向右读取，并在已读前缀的右侧继续输入。研究双向自动机、从右向左读取或代数识别时，会出现相应的左商或双边同余；不能不加说明地互换方向。

推论与应用

DFA 最小化计算的正是可达状态的未来语言等价：分割细化从接受/拒绝开始，反复用字符转移暴露区分后缀，直到每一块对应一个 Nerode 类。最小结果可作为正则语言的规范表示，用于等价检查、缓存与代码生成。

状态下界也可直接由区分族给出。找出 $k$ 个两两可区分前缀，就证明任何 DFA 至少有 $k$ 个状态；给出无限族则证明语言不正则。与正则语言泵引理相比，Myhill–Nerode 是充要刻画并能给出精确状态数，而泵引理只提供所有正则语言必须满足的循环性质，有时更容易套用，却不能证明正则性。

残余语言还连接自动机学习。查询学习算法逐步提出后缀实验来区分观察到的前缀，反例则暴露尚未分开的残余；当表中的行稳定且闭合时，得到的假设 DFA 正是在逼近 Nerode 商。

参考资料

John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed., Pearson, 2006, §4.4.
Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013, §1.2.
Dexter Kozen, Automata and Computability, Springer, 1997.

形式陈述 ​

从 DFA 得到有限指标 ​

从有限指标构造 DFA ​

反向链接

形式陈述

从 DFA 得到有限指标

从有限指标构造 DFA