迈希尔－尼罗德定理

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

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

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

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

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

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

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

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

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

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

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