迈希尔-尼罗德定理

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

这个定理得名于 John MyhillAnil Nerode,他们于1958年在芝加哥大学证明了这个定理[1]

定理陈述

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

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

定理证明

  • 方向一:如果    所切分出的等价类数目是无限多的,那么语言   无法正规

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

  • 方向二:如果    所切分出的等价类数目是有限的,那么必存在一台同等数量状态的 DFA 可辨识   使其正规

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

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

用途和结论

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

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

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

再给一例,我们想说明   不是正规的。原因是,给定任意两个不同长度的   字串,我们都能接上一个后接字串将这两个字串分辨开来,举例来说,给定   ,我们就能接上    合法而   不合法。所以有无限多个字串     、... 等彼此之间都是可分辨的,这意味着需要无限多个状态的自动机才能辨识这个语言,和正规语言定义矛盾,因此   不是正规语言。

引用

注释

  1. ^ A. Nerode, "Linear automaton transformations", Proceedings of the AMS, 9 (1958) pp 541-544.
  2. ^ Edmund M. Clarke, Myhill-Nerode Handout页面存档备份,存于互联网档案馆 (2009)

一般参考

  • 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)