迈希尔-尼罗德定理

在形式语言理论中，Myhill–Nerode 定理提供了一个语言是正则语言的必要和充分条件。它近乎专门的被用来证明一个给定语言不是正则的。

这个定理得名于 John Myhill 和 Anil Nerode，他们于1958年在芝加哥大学证明了这个定理。

定理陈述

给定一个字母集 (alphabet) $\Sigma$ 以及其生成的语言 (language) $L\subseteq \Sigma ^{*}$，我们先来定义两个字串 $x,y\in \Sigma ^{*}$ 之间彼此的关系：如果对于所有的后接字串 $z\in \Sigma ^{*}$ (注意！$z$ 可以是空字串) 都会让 $xz$ 和 $yz$ 同时属于或不属于 $L$，那么我们说 $x$ 和 $y$ 不可区分 (indistinguishable)；相反地如果存在某个后接字串 $z\in \Sigma ^{*}$ 让 $xz$ 和 $yz$ 其中一个属于而另外一个不属于 $L$，则我们说 $x$ 和 $y$ 是可区分的 (distinguishable)。如果 $x$ 和 $y$ 不可区分，我们说它们满足关系 (relation) $R_{L}$，数学式子写成 $x\ R_{L}\ y$。我们也很容易证明这种关系是种等价关系 (equivalence relation)，因此它可以把 $\Sigma ^{*}$ 划分成一个或多个等价类 (equivalence class)。

Myhill–Nerode 定理声称一套语言 $L$ 是正规的“当且仅当”$\Sigma ^{*}$ 被 $R_{L}$ 所切分出的等价类数目是有限的，此外这个等价类数量又恰好是可辨识 $L$ 的最小 DFA 的状态数量。在详细的证明中“一个等价类会恰好对应到最小 DFA 里的一个状态”，如果先给定一个自动机，则任意两个能驱使它走到同一个状态的字串 $x$ 和 $y$ 必在同一个等价类中；如果先给定一个等价类划分，那可以轻易地构造出一个自动机使其状态恰好对应到等价类。

定理证明

• 方向一：如果 $\Sigma ^{*}$ 被 $R_{L}$ 所切分出的等价类数目是无限多的，那么语言 $L$ 无法正规

这个方向比较简单，我们只要证明一个引理 (lemma)：可辨识 $L$ 的 DFA 状态数量必须不小于等价类数目即可，而这可以使用反证法 (鸽笼原理) 说明。如果 DFA 状态数量少于等价类数量，那代表必定有两个不属于同一个等价类的字串 $x$ 和 $y$ 会引导 DFA 到同一个状态，如果它们又继续有后接字串 $z$，就会让 $xz$ 和 $yz$ 也走到同一个状态，如此一来根据定义，$x$ 和 $y$ 应该要属于同一个等价类，造成矛盾，因此 DFA 状态数量必须不小于等价类数目。由这个结论可以推得，当等价类数目无限多时，这个 DFA 的状态数量也必须是无限多，和“有限”状态机的定义矛盾，换句话说我们找不到一台 DFA 可辨识 $L$，因此 $L$ 不正规。

• 方向二：如果 $\Sigma ^{*}$ 被 $R_{L}$ 所切分出的等价类数目是有限的，那么必存在一台同等数量状态的 DFA 可辨识 $L$ 使其正规

我们先构造出一台 DFA，先假设它的每一个状态都刚好代表一个等价类 (也就是一个状态承装一个等价类里的所有字串，从起点开始输入该字串务必到达该状态)，而转移函数的决定方式就是从一个状态随意抓取一个代表字串，看看它吃了一个字母之后的字串会落在哪个状态里面，就让它走去那里。这个走向会唯一，理由很简单可以自己想。对于每个状态和每个转移字母都穷举一遍，最后再观察哪些状态包含了被接受的字串，直接让它们变成终点态 (final state)。一个等价类里如果有一个字串被接受，那同一个类里的所有其他字串也会通通被接受，因为根据定义，后接字串可以是空字串。到目前为止，我们有了一定数量的状态 (圆圈圈)、所有的转移函数、一个唯一的起点 (看空字串在哪里即可)、所有的终点，是一台合法的 DFA。现在的问题是，要怎么证明这台 DFA 能确实辨识 $L$，也就是说对于任意字串输入都能驱使 DFA 走到我们当初赋予每个状态必须各自代表一个等价类的任务？

这必须对字串输入的长度作数学归纳法才能证明。如果字串输入长度为 0，也就是空字串，那它必须留在起点，而我们起点的取法就刚好是看空字串的位置，所以输入为空字串时的状态落点正确；如果对于所有长度不超过 $\ell$ 的字串输入，它们的状态落点皆正确，那么对于任何长度为 $\ell +1$ 的字串输入 $w$，皆可分解为 $w=ua$，其中 $u$ 的长度为 $\ell$ 而 $a$ 的长度为 $1$ (字元)，走完 $u$ 之后的落点根据假设是正确的，剩下的一个字元 $a$ 根据我们上述决定转移函数的方式，自然也会继续走向我们当初所期望的落点；如此依序递回下去，就能说明对于任意字串输入，这台 DFA 确实能妥善的把 $\Sigma ^{*}$ 里的每个字串分到正确的类别，并决定接受与否。于是乎我们根据这个 $R_{L}$ 创造了一台能辨识 $L$ 的 DFA，而且这台 DFA 的状态数量刚好就是 $\Sigma ^{*}$ 被 $R_{L}$ 所切分出的等价类数量。

用途和结论

Myhill–Nerode 定理的一个结论是语言 L 是正则的(就是说可被有限状态机接受)，当且仅当 R_L 的等价类的数目是有限的。

直接推论是如果一个语言定义等价类的无限集合，它就不是正则的。这个推论经常被用来证明一个语言不是正则的。

例如，由可以被 3 整除的二进制数组成的语言是正则的。有三个等价类 3 - 被 3 除的时候余数是 0, 1 和 2 的数。接受这个语言的极小自动机有对应于等价类的三个状态。

再给一例，我们想说明 $A=\{0^{n}1^{n}:n\geq 0\}$ 不是正规的。原因是，给定任意两个不同长度的 $0$ 字串，我们都能接上一个后接字串将这两个字串分辨开来，举例来说，给定 $000$ 和 $00000$，我们就能接上 $111$ 让 $000111$ 合法而 $00000111$ 不合法。所以有无限多个字串 $0$、$00$、$000$、$0000$、... 等彼此之间都是可分辨的，这意味着需要无限多个状态的自动机才能辨识这个语言，和正规语言定义矛盾，因此 $A$ 不是正规语言。

引用

一般参考

• John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-02988-X. (See chapter 3.)
• Tom Henzinger, Lecture 7: Myhill–Nerode Theorem (2003)