形式陈述
给定语言 L ⊆ Σ ∗ ,在所有字上定义 Nerode 关系
x ≡ L y ⟺ ∀ z ∈ Σ ∗ , x z ∈ L ⟺ y z ∈ L . 它是等价关系 理路 等价关系 Equivalence relation 满足自反、对称和传递性的关系。 ,并且对右拼接稳定:若 x ≡ L y ,则对任意 w 都有 x w ≡ L y w 。等价地,定义语言对前缀 x 的左商(也称前缀残余)
x − 1 L = { z ∈ Σ ∗ : x z ∈ L } , 就有 x ≡ L y 当且仅当 x − 1 L = y − 1 L 。
Myhill–Nerode 定理断言:
L 是正则语言 理路 正则语言 Regular language 存在有限状态识别器的有限字语言,也就是只需固定有限种前缀摘要即可判断的语言。 ,当且仅当 ≡ L 的等价类个数有限;
若类数为 k ,识别 L 的最小完整 DFA 恰有 k 个可达状态;
删除不可达状态后,最小 DFA 在保持初态、转移与接受状态的同构意义下唯一。
从 DFA 得到有限指标
设 DFA M = ( Q , Σ , δ , q 0 , F ) 识别 L 。若
δ ∗ ( q 0 , x ) = δ ∗ ( q 0 , y ) , 那么从这个共同状态继续读取任意 z 会到达同一终点,因此 x z 与 y z 必然同时接受或同时拒绝,即 x ≡ L y 。于是每个可达 DFA 状态承载至多一种未来行为,而 Nerode 类数不超过可达状态数。特别地,任何识别 L 的 DFA 至少需要与 Nerode 类一样多的状态。
注意逆命题对一台未最小化 DFA 未必成立:两个不同状态可能对所有后缀行为完全相同。机器可以人为复制状态,语言的 Nerode 关系不会因此产生新类。
从有限指标构造 DFA
反过来,若 ≡ L 只有有限多个类,就以商集 理路 商集 Quotient set · Set of equivalence classes 等价关系的所有等价类组成的集合。 中的这些类本身为状态:
Q L = Σ ∗ / ≡ L , q 0 = [ ε ] , δ L ( [ x ] , a ) = [ x a ] , F L = { [ x ] : x ∈ L } . 若 [ x ] = [ y ] ,右不变性保证 [ x a ] = [ y a ] ,所以转移不依赖代表元;在等价定义中取 z = ε ,又可知一个类不会同时含有 L 内外的字,所以 F L 也定义良好。对字长归纳得到
δ L ∗ ( [ ε ] , x ) = [ x ] , 商自动机因而恰好识别 L 。它每个 Nerode 类使用一个状态,达到前一方向给出的下界,所以最小。
任何可达最小 DFA 的状态都由某个前缀到达。把该状态映到这个前缀的 Nerode 类,映射保持初态、转移和接受性;若两个状态落在同一类,就可继续合并而不改变语言,与最小性矛盾。映射因此为双射,也证明最小 DFA 的唯一性。
直觉
读完前缀后,过去只通过一份“哪些后缀仍能成功”的未来清单影响判断,原来的字符序列已经无需保留。两个前缀若清单相同,任何识别器都没有理由继续区分它们;若清单不同,就存在一个具体后缀揭示差异,合并它们必定让至少一个完整字判断错误。
最小 DFA 的状态不是设计者凭经验挑出的标签,而是语言所有不同残余的规范名字。转移 [ x ] → a [ x a ] 表示读一个符号会怎样更新未来清单,接受态则是包含空后缀的残余。定理由此直接从语言语义读出最低记忆量,无需先猜一台自动机再证明它最小。
“可区分”必须针对右侧续写:找到 z 使 x z ∈ L 而 y z ∉ L ,就证明 x ≢ L y 。区分后缀可以依赖于所比较的一对前缀;不要求一条万能测试串同时区分所有状态。反过来,只试过若干短后缀而未发现差异,并不能证明等价。
图片加载失败 Nerode 三类与最小 DFA
例子与边界
四个残余与六条区分证书
考虑在 Σ = { a , b } 上的语言 L = a ∗ b ( ε ∣ b ) 。确定化 理路 DFA–NFA 等价定理 DFA–NFA equivalence · Subset construction 每个 NFA 都能以当前可能状态集为一个 DFA 状态,从而在有限字上保持语言不变。 为它生成了五个可达子集,最小化 理路 有限自动机最小化 Finite automaton minimization · DFA minimization 删除不可达状态并按全部未来后缀的行为划分状态,构造识别同一语言的唯一最小 DFA。 又把其中两个合并成四态机器。这里从语言本身出发回答:四态是否已经达到任何完整 DFA 都无法突破的下界?
列出每种前缀仍允许的续写,就得到全部残余:
前缀形状
代表 x
左商 x − 1 L
对应商状态
a ∗
ε
a ∗ b ( ε ∣ b )
U
a ∗ b
b
{ ε , b }
V
a ∗ b b
b b
{ ε }
W
其余字
b b b
∅
X
第一行可以继续读若干 a ,但最终必须补一个或两个 b ;第二行可以立即结束,也可以再补一个 b ;第三行只能结束;最后一行已经违反形状约束,任何续写都无法修复。四种前缀形状穷尽 Σ ∗ ,因此残余至多四种。注意 ε 与 a 有相同残余,尽管子集 DFA 分别把它们送到不同状态 A , B ;Nerode 类描述未来语言,不描述某张 NFA 图里当前有哪些结点活跃。
接着证明这四个残余确实不同。下面逐对选择后缀 z ,把连接后的两个完整字及判断同时列出,避免只凭状态名称断言可区分。
前缀 x , y
后缀 z
完整字 x z
完整字 y z
ε , b
ε
ε ∉ L
b ∈ L
ε , b b
ε
ε ∉ L
b b ∈ L
ε , b b b
b
b ∈ L
b b b b ∉ L
b , b b
b
b b ∈ L
b b b ∉ L
b , b b b
ε
b ∈ L
b b b ∉ L
b b , b b b
ε
b b ∈ L
b b b ∉ L
若任意完整 DFA 用少于四个状态,由鸽巢原理 理路 鸽巢原理 Pigeonhole principle · Dirichlet's box principle 把多于 n 个对象放入 n 个容器时,至少一个容器包含两个对象。 ,四个代表前缀必有两个到达同一状态;再接表中对应的区分后缀,机器就会对一个应接受、一个应拒绝的字给出相同结果。这是直接的下界矛盾。四残余商给出四态上界,故最小完整 DFA 恰有四态。
空残余也必须计入这个结论,因为完整机器读取 b b b 后仍必须处在某个状态。若允许“缺边立即拒绝”的部分 DFA,可以省去空残余状态,本例只画三个状态。三个非空残余仍两两可区分,而且各自存在可接受续写,所以不能连这些状态也省去;因此本例的最小部分表示恰为三态。两种数字对应不同的转移约定。
其他例子与边界
令
含 子 串 L = { w ∈ { a , b } ∗ : w 含子串 a b } . 前缀的未来行为恰分三类:尚未出现 ab 且末尾不是 a,可由 ε 代表;尚未出现 ab 且末尾是 a,可由 a 代表;已经出现 ab,可由 ab 代表。第一、第二类由后缀 b 区分,因为 b 不含 ab 而 ab 含;第三类与前两类都可由空后缀区分,因为它已经接受。于是最小 DFA 恰有三个状态:无候选前缀、刚见到候选 a、已经匹配成功。
这份论证同时给了上界和下界。三类描述覆盖所有前缀,故商自动机至多三状态;三个代表两两可区分,故任何 DFA 至少三状态。只展示一台三状态 DFA 只能证明上界,若没有区分证书,不能排除还存在两状态实现。
考虑复制语言
C = { x # x : x ∈ { 0 , 1 } ∗ } . 前缀集合 { x # : x ∈ { 0 , 1 } ∗ } 两两可区分:对不同的 x , y ,接后缀 x 后有 x # x ∈ C ,而 y # x ∉ C 。因此 C 有无限多个 Nerode 类,不是正则语言。这个证书准确指出有限状态缺失的信息:分隔符前的整段任意长文本必须留到后半段逐字核对。
关系是右同余,因为标准自动机从左向右读取,并在已读前缀的右侧继续输入。研究双向自动机、从右向左读取或代数识别时,需要重新说明等价关系对哪一侧拼接稳定,或改用双边同余。本页的关系是右同余,而 x − 1 L 按商运算名称称为左商;这两个“左右”描述不同操作,不能混用。
推论与应用
DFA 最小化 理路 有限自动机最小化 Finite automaton minimization · DFA minimization 删除不可达状态并按全部未来后缀的行为划分状态,构造识别同一语言的唯一最小 DFA。 计算的正是可达状态的未来语言等价:分割细化从接受/拒绝开始,反复用字符转移暴露区分后缀,直到每一块对应一个 Nerode 类。最小结果可作为正则语言的规范表示,用于等价检查、缓存与代码生成。
状态下界也可直接由区分族给出。找出 k 个两两可区分前缀,就证明任何 DFA 至少有 k 个状态;给出无限族则证明语言不正则。与正则语言泵引理 理路 正则语言泵引理 Pumping lemma for regular languages 足够长的正则语言成员必有一段位于短前缀中的非空环,可删除或重复任意多次而仍留在语言中。 相比,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.
Dexter Kozen, Automata and Computability , Springer, 1997.