动机
名称不同的两个状态未必代表不同的信息。如果对每一种可能的后续输入,两个状态给出的接受或拒绝结果都相同,那么读这台机器的人就可以放心地把它们视为同一个状态。反过来,只要存在一个能区分它们的后续输入,就证明这两个状态不能被等同。本节把这一观察转化为一个规范的构造和一个有限的算法。这里的自动机都是确定型且完全的;缺失的转移必须先指向一个拒绝陷阱状态。
定义
定义 1.1.1
(剩余语言与前缀等价)
固定有限字母表 和语言 。 在词 之后的剩余语言(residual)为 。当 时,记 。
定义 1.1.2
(状态等价、可达与最小性)
对于 DFA,如果两个状态接受的后续输入恰好相同,则称它们等价。如果存在某个词把初始状态带到某个状态,则称该状态可达。最小性指在识别 的完全 DFA 中状态数最少。
右同余性质由此直接得到:若 ,则对每个字母 有 ,因为 当且仅当 。请注意, 与 本身不必属于 ;剩余语言检验的是每一个后续输入,包括 。
定理
定理 1.1.3
(Myhill–Nerode 定理)
语言 能被某个有限 DFA 识别,当且仅当 只有有限多个等价类。在这种情形下,以这些等价类为状态、初始状态为 、转移为 、接受状态为满足 的 的 DFA,是 的一个最小完全 DFA。 的每个最小完全 DFA 都与它同构(作为带初始状态、带标记并带接受状态集的自动机)。
定理 1.1.4
(划分细化)
给定一个有限完全 DFA,先删除不可达状态。从接受状态集和非接受状态集中,只保留非空者作为初始划分。只要某个块中的两个状态在某个字母上的转移落入当前不同的块,就拆分该块。当不再有可拆分的块时,这些块恰好就是状态等价类。其商 DFA 对原语言而言是最小的。
证明思路
证明
(剩余语言类给出最小 DFA)
先设某个 DFA 识别 。如果读入 与读入 到达同一个状态,那么每个后续输入的结果都相同,因此 。所以剩余语言的等价类个数不超过状态数。反过来,当等价类只有有限多个时,上述构造由右同余性而是良定义的;接受性也是良定义的,因为 是一个可能的后续输入。对 归纳可知,读入 之后所处的状态是 。因此它识别 。
的任何 DFA 对不同等价类中的词必定到达不同的状态,这给出下界。所构造的机器达到这个下界。若另一台机器也达到这个下界,则它的所有状态都可达:否则删除不可达状态会得到更小的机器。把读入 后到达的状态映到 的映射是良定义的、满射的,并且由于两边基数有限且相等,它是双射。它保持初始状态、转移和接受性。这证明了唯一性是在重命名意义下成立的,而不是状态名称逐字相同。
证明
(稳定划分就是等价类)
对于细化算法:起初没有任何块同时包含接受状态和拒绝状态,所以等价的状态不会被分开。如果某次拆分在字母 上把 分开,则它们的后继所在的块此前已被分开;由归纳可知,存在某个后缀 区分这两个后继,于是 区分 。因此等价的状态永远不会被拆开。算法终止时,同一块中的状态在每个字母上的后继都在同一块中,并且接受性一致。现在对后续输入的长度归纳,即知它们等价。每次真正的拆分都使块数增加,而块数至多是可达状态的个数,所以过程会终止。商自动机通过对输入长度归纳而识别同一语言,并且它的不同状态是可区分的。因此由第一个定理,它是最小的。
证明透视
为什么每个后缀都重要
对空后续输入取得一致,只检验了当前的接受性。细化步骤多检验了一个起始字母,然后依赖一个任意的后缀。归纳覆盖了每一个有限的后续输入,尽管算法只存储有限多个块。
假设在三处起作用。转移函数的完全性使 对每个状态和每个词都有定义,所以每个后续输入都能被检验。状态集的有限性限制了拆分的次数,这就是过程会停止的原因。关键一步在于见证的记录:只有存在一个真正区分两个状态的后缀 ,才会作出拆分,所以等价的状态对永远不会被拆开,而稳定性则给出反方向。若去掉完全性,就会有些后续输入没有被检验。
例题详解
例题 1.1.5
(偶数个 1 的奇偶性)
在 上,令 为含有偶数个 1 的词的集合。剩余语言有两个:偶数个 1 的前缀之后,后续输入需要偶数个 1;奇数个 1 的前缀之后,后续输入需要奇数个 1。它们在 上不同。因此最小机器有两个状态: 使状态保持不变, 使两个状态互换,偶数状态既是初始状态又是接受状态。
例题 1.1.6
(一次细化分开两个拒绝状态)
考虑字母表 和状态 ,初始状态为 ,唯一的接受状态为 ,转移为 、、。所有状态均可达。起初的块是 与 。第一个块会被拆分,因为 转移到前者,而 转移到后者。三个单元素块是稳定的。后缀 区分 与 ,而 区分它们中任何一个与 。
例题 1.1.7
(需要无限多个状态的语言)
对于 ,对不同的非负整数 ,前缀 与 被 区分:,但 。因此剩余语言有无限多个,没有有限 DFA 识别 。这个证明是为每一对前缀选取一个区分后缀,而不是应用泵引理。
常见错误
反例模式
当前答案相同并不意味着状态相同
在三状态的例子中, 与 对空后续输入都拒绝,但从 出发 被接受,从 出发则被拒绝。仅仅因为二者当前都拒绝就把它们合并,会改变所识别的语言。
常见错误
(不要忘记删除不可达状态)
删除不可达状态是对给定机器进行最小化的必要步骤。如果合并了等价的可达状态,却没有删除某个不可达的孤立状态,结果可能不是最小的。
反过来,商中的一个块可以包含多个状态而不丢失信息:它的转移是良定义的,恰恰因为最终的划分是稳定的。
理解并实现细化
可以把细化看作一系列要求越来越高的实验。起初,两个状态只要对空后续输入的表现一致,就留在一起。经过一次同时细化后,状态还须对所有长度为一的后续输入表现一致。经过 轮后,它们对长度至多为 的后续输入表现一致。这个断言由归纳得到:长度至多为 的后续输入或者为空,或者形如 ,其中 的长度至多为 。要使它们对所有这样的字符串都一致,对每个 ,其 -后继必须直到第 轮都一致。
这种解释假定每一轮都是从上一轮的划分同时进行的。实现时也可以一次拆分一个块;它会到达同一个稳定划分,但其中间划分不必与按长度编号的各轮一致。无论采用哪种实现,算法在每次拆分之后都必须继续检查每个字母,因为后继之间新出现的区分,可能揭示出其前驱之间更早就存在的区分。
对于小型自动机,可以构造一张由可达状态的无序对组成的表。把接受性不一致的每一对都标记出来,以 作为见证。每当某个未标记的对的 -后继已经被标记并带有见证 ,就用见证 标记该对。继续下去,直到再没有对可被标记。未标记的对由同样的稳定划分论证可知是等价的。见证在检查实现时很有用:它们给出一个具体的输入,说明合并某一对状态会出错。除非按适当的长度顺序处理各对,否则这些见证不一定是最短的。
例题 1.1.8
(细化向后传播)
取四个一元状态 ,其中 为初始状态, 是唯一的接受状态,当 时 把每个 移到 ,而 自循环。所有状态均可达。初始划分为 。一次同时细化把后继为接受状态的 与 分开。下一轮把 与 分开,因为它们的后继现在位于不同的块中。后缀 区分 与 :从前者出发到达 ,从后者出发到达 。四个状态都是必需的。
商对每个原有转移的定义为 。稳定性保证结果不依赖于代表元 的选取。对每个词 ,归纳得到 。因此,商所做的不止是保留从初始状态出发对完整输入的接受性:它保持了每个原有状态对每个未来输入的行为。这说明了为什么在计算过程中合并这些状态是合理的,而不是只有在读完整个词之后才合理。
还有一个有用的区别:固定自动机中状态的等价,不同于语言的前缀的等价。状态等价问的是,把任意一个状态用作起点时会发生什么。前缀等价问的是,从真正的初始状态出发,一个前缀之后跟着什么样的剩余语言。每个可达状态至少对应一个前缀,并且它的后续语言恰好就是该前缀的剩余语言。不可达状态也有后续语言,但它们不能贡献从真正的初始状态出发所到达的新的剩余语言,因此不属于规范的最小机器。
语言的比较
规范机器还给出了判定同一字母表上两个给定完全 DFA 是否等价的一个判定过程。把它们的不交并看作一个转移系统,按接受性和转移细化合并后的状态集,然后比较两个初始状态。当且仅当每个词要么被两者都接受、要么被两者都拒绝时,它们才在最终的同一个块中。与先分别最小化每台机器、再比较名称不同,这一过程不假定任何特定的命名约定。在配对表方法中,若初始状态对被标记,就给出一个明确的词,见证二者不等价。在合并字母表不同的机器之前,应先指定一个共同的字母表,并用陷阱状态补全转移函数;否则“同一语言”还没有在同一个定义域上被提出。
例如,含有偶数个 1 的词的语言,在插入一个冗余状态后保持不变,只要该状态的接受性与后继行为与原来的偶数状态完全一致。这样的重复不改变任何后续语言,因此只要两者都可达,细化就会把重复的状态与原状态合并。相反,如果添加的新状态在某个字母上的转移不同,那么这两个状态也许要再读入若干字母之后才变得可区分。只有当目标状态已经等价时,转移的直接相等才足以保证等价,而不是仅仅因为标签看起来相似。
有限见证与算法的适用范围
有限状态这一假设在算法中起两次作用。第一,可达性可以通过图搜索来计算:从初始状态出发,反复加入已到达状态的每个字母后继。由于状态有限,这一过程会停止。第二,可达状态集的可能拆分只有有限多种。因此稳定划分在有限次改变之后就会出现。正确性的证明并不需要预先知道最短区分词长度的界,尽管有限的配对表在标记一个对时本身就能给出这样的见证。
这个定理是关于所有语言的陈述,包括非正则语言。它的正向蕴涵把有限机器变成有限多个剩余语言。它的反向蕴涵由有限多个剩余语言构造出一台机器。要用这个定理证明非正则性,只需给出一族无限多个前缀,使它们的剩余语言两两不同即可。不需要列出每一个剩余语言,也不需要找到计算它们的算法。另一方面,检查少数几个可区分前缀的例子,并不能证明存在无限多个等价类:这个两两的论证必须对任意多个不同的下标都成立。
常见错误
(少数几个可区分的前缀不能证明有无限多个等价类)
对于 ,检查 、、 两两可区分,只说明至少需要三个状态。非正则性的证明必须对任意的 给出区分后缀 (如例题详解所示),这样等价类的个数才没有上界。
只有在固定了输入字母表和完全性约定之后,最小机器才是唯一的。如果允许部分自动机在缺失转移时拒绝,那么拒绝陷阱状态有时可以省略,从而改变状态数。这里的构造使用全转移函数,对于“无望”的前缀,其剩余语言是空语言。只要到达这个空剩余语言,它就是一个普通的状态。类似地,改变字母表可能引入新的可能后续输入;比较时应明确给出共同的字母表。
作为最后的检验,考虑空语言。所有前缀都具有同一个空剩余语言,所以它的最小完全 DFA 恰有一个非接受状态,并在每个字母上自循环。包含所有词的语言也只有一个状态,但该状态是接受状态。两台机器的状态数都不是零:DFA 必须有一个初始状态,即使在某个特定输入词中字母表没有可用的转移时也是如此。这个小例子同时检验了对初始状态和空后续输入的处理。
总结
剩余语言恰好刻画了一个前缀中能够影响未来接受性的那部分信息。它们的个数就是正则语言的状态复杂度。细化在有限机器上计算同一个等价关系,而一个区分后缀就是某个拟议的合并有误的证据。
下图使用另一台五状态二元字母表自动机,并非上面的单字母例子。可比较它的可达状态细分与那些例子。
练习
快速检查
(求以 结尾的二进制词的最小完全 DFA,并说明空串的状态。)
想一想:状态需要记住最后读入的符号的什么信息。
解答 · 答案
用状态 表示最后一个符号是否为 ; 是初始状态且拒绝, 接受。输入 使任一状态转到 ,输入 使任一状态转到 。它们被 区分,这证明了最小性。
快速检查
(对 ,当 时,给出区分 与 的后缀。)
选取恰好能补全较短前缀所对应的 的个数的后缀。
解答 · 答案
取 。此时 ,而 ,因为 。这包括 的情形,此时后缀为 。
快速检查
(解释为什么一个不接受任何后续输入的可达状态,可以与任何具有同样性质的其他可达状态合并。)
比较这两个状态的剩余语言。
解答 · 答案
两个状态的剩余语言都是空语言,所以它们等价。商构造保持所有后续输入;可达性并不妨碍安全地合并。
快速检查
(对于一元词,证明长度可被 整除的语言至少需要三个状态。)
考虑前缀 、、。
解答 · 答案
之后的剩余语言为 。若 ,取 使 ;则 在 之后被接受,在 之后则不被接受。因此 三个前缀的剩余语言两两不同,这给出下界;由三个状态构成的环达到这个下界。