形式陈述

给定字母表 $\Sigma$$\mathrm{\Sigma }$ 上的语言 $L$$L$，定义右同余关系

$$ x\equiv_L y \quad\Longleftrightarrow\quad \forall z\in\Sigma^*,\;xz\in L\iff yz\in L. $$$$x{\equiv }_{L}y⟺\mathrm{\forall }z\in {\mathrm{\Sigma }}^{\ast },xz\in L⟺yz\in L.$$

Myhill–Nerode 定理断言：$L$$L$ 是正则语言，当且仅当 $\equiv_L$${\equiv }_L$ 只有有限多个等价类；若有限，其等价类数恰等于识别 $L$$L$ 的最小 DFA 状态数。一个方向把 DFA 到达同一状态的字符串合并；另一方向以等价类为状态，令 $[x]\xrightarrow{a}[xa]$$[x]\stackrel{a}{\to }[xa]$，右同余性保证转移良定义。

直觉

两个前缀等价，表示无论以后接什么后缀，语言都无法再区分它们。最小自动机的每个状态因此代表一种不可互相替代的“未来行为”。

例子与边界

对 $L=\{w\in\{0,1\}^*:w\text{ 中 }1\text{ 的个数为偶数}\}$$L=\{w\in \{0,1{\}}^{\ast }:w\text{ 中 }1\text{ 的个数为偶数}\}$，前缀只有“当前奇数个”和“当前偶数个”两类，所以最小 DFA 有两个状态。若语言 $\{0^n1^n:n\ge0\}$$\{0^n{1}^n:n\ge 0\}$，前缀 $0^i$$0^i$ 两两可由后缀 $1^i$$1^i$ 区分，等价类无限，故语言不正则。只展示许多可区分前缀可证明状态下界；必须得到无限族才可直接否定正则性。

推论与应用

该定理同时给出正则性的判定刻画、DFA 最小化的语义基础和状态复杂度下界。区分字符串集合与表填充算法都在寻找不同 Nerode 类；它比泵引理更接近充要条件。

参考资料

• John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed., Pearson, 2006，Ch. 4, equivalence of strings and minimization of finite automata。
• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013，Ch. 1, Myhill–Nerode theorem and distinguishability。