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

例子与边界

四个残余与六条区分证书

考虑在 $\Sigma=\{a,b\}$ 上的语言 $L=a^*b(\varepsilon\mid b)$ 。确定化为它生成了五个可达子集，最小化又把其中两个合并成四态机器。这里从语言本身出发回答：四态是否已经达到任何完整 DFA 都无法突破的下界？

列出每种前缀仍允许的续写，就得到全部残余：

前缀形状	代表 $x$	左商 $x^{-1}L$	对应商状态
$a^*$	$\varepsilon$	$a^*b(\varepsilon\mid b)$	$U$
$a^*b$	$b$	$\{\varepsilon,b\}$	$V$
$a^*bb$	$bb$	$\{\varepsilon\}$	$W$
其余字	$bbb$	$\varnothing$	$X$

第一行可以继续读若干 $a$ ，但最终必须补一个或两个 $b$ ；第二行可以立即结束，也可以再补一个 $b$ ；第三行只能结束；最后一行已经违反形状约束，任何续写都无法修复。四种前缀形状穷尽 $\Sigma^*$ ，因此残余至多四种。注意 $\varepsilon$ 与 $a$ 有相同残余，尽管子集 DFA 分别把它们送到不同状态 $A,B$ ；Nerode 类描述未来语言，不描述某张 NFA 图里当前有哪些结点活跃。

接着证明这四个残余确实不同。下面逐对选择后缀 $z$ ，把连接后的两个完整字及判断同时列出，避免只凭状态名称断言可区分。

前缀 $x,y$	后缀 $z$	完整字 $xz$	完整字 $yz$
$\varepsilon,b$	$\varepsilon$	$\varepsilon\notin L$	$b\in L$
$\varepsilon,bb$	$\varepsilon$	$\varepsilon\notin L$	$bb\in L$
$\varepsilon,bbb$	$b$	$b\in L$	$bbbb\notin L$
$b,bb$	$b$	$bb\in L$	$bbb\notin L$
$b,bbb$	$\varepsilon$	$b\in L$	$bbb\notin L$
$bb,bbb$	$\varepsilon$	$bb\in L$	$bbb\notin L$

若任意完整 DFA 用少于四个状态，四个代表前缀必有两个到达同一状态；再接表中对应的区分后缀，机器就会对一个应接受、一个应拒绝的字给出相同结果。这是直接的下界矛盾。四残余商给出四态上界，故最小完整 DFA 恰有四态。

空残余也必须计入这个结论，因为完整机器读取 $bbb$ 后仍必须处在某个状态。若允许“缺边立即拒绝”的部分 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 类，不是正则语言。这个证书准确指出有限状态缺失的信息：分隔符前的整段任意长文本必须留到后半段逐字核对。

关系是右同余，因为标准自动机从左向右读取，并在已读前缀的右侧继续输入。研究双向自动机、从右向左读取或代数识别时，需要重新说明等价关系对哪一侧拼接稳定，或改用双边同余。本页的关系是右同余，而 $x^{-1}L$ 按商运算名称称为左商；这两个“左右”描述不同操作，不能混用。

推论与应用

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

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

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

参考资料

M. O. Rabin and D. Scott, “Finite Automata and Their Decision Problems”, 1959，印刷第 118 页，Theorem 2 (Nerode) 与 Corollary 2.1：有限指标右不变关系及最少状态数。
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

四个残余与六条区分证书

其他例子与边界