动机
有限自动机所描述的语言可能是无穷的,但关于该语言的许多问题,只需检查一个有限图就能回答。可达性判定是否存在被接受的单词;乘积图用于比较两台机器;而有用环则区分有限语言与无穷语言。这些算法还会给出证书:一个被接受的单词、一个区分单词,或一条可以重复的经过环的路径。
这里的机器都是定义在同一有限字母表上的完全确定有限自动机。自动机的底层图保留带标号的转移。搜索时,可达性不考虑标号,但要把一条路径还原成单词,则需要用到标号。
定义
定义 1.3.1
(确定有限自动机与接受)
一个 DFA 是 ,其中 为有限状态集, 为初始状态, 为接受状态集, 为全转移函数。扩展转移 通过依次沿 的各个字母转移来定义。一个单词被接受,是指从 出发读完该单词后停在 中。
定义 1.3.2
(可达、可共达与有用环)
若存在从 出发的路径到达某状态,则称该状态可达。若从某状态出发存在路径到达接受状态,则称该状态可共达。若一个有向环位于某条从初始状态到接受状态的路径上,则称它是有用的;等价地说,它的各顶点既可达又可共达。环必须至少包含一条转移。空单词标记一条长度为零的路径,但在此处不算作环。
定义 1.3.3
(三个判定问题)
- 空性。输入:DFA 。输出: 是否成立;若语言不为空,同时给出一个被接受的单词。
- 等价性。输入:同一字母表上的两个完全 DFA 。输出: 是否成立;若不成立,同时给出恰被其中一个接受的单词。
- 无穷性。输入:DFA 。输出: 是否无穷;若是,同时给出带标号的进入路径、环与离开路径。
定理
定理 1.3.4
(空性与等价性)
一个 DFA 的语言为空,当且仅当没有接受状态可达。定义在同一字母表上的两个完全 DFA 等价,当且仅当它们的乘积中没有恰好含一个接受分量的可达状态。广度优先搜索或者判定相应的性质,或者返回一个最短的见证单词。
证明
(搜索次序与乘积状态)
每个单词标记一条从初始状态出发的路径,而每条路径上的标号也构成一个单词。该单词被接受,当且仅当路径的终点是接受状态,这就证明了空性判据。广度优先搜索按路径长度非递减的顺序探索状态;若存在到达接受状态的路径,则沿前驱边可以还原出一条最短路径。
对于等价性,读入 之后的乘积状态为 ,这可对 的长度归纳得到。在区分检验中,当一个状态对恰好有一个分量为接受时,将其标记。若一个被标记的状态对可达,则到达它的单词恰好被其中一台机器接受;反之,每个区分单词都会到达这样的状态对。因此,搜索有限的乘积图即可判定等价性,并且在不等价时返回一个最短的区分单词。
证明思路
定理 1.3.5
(无穷性判据)
一个 DFA 的语言是无穷的,当且仅当其转移图中存在有用的有向环。若该自动机有 个状态且其语言是有限的,则每个被接受的单词的长度都小于 。
证明
(重复有用环,以及鸽巢原理)
若存在有用环,则取一条从初始状态到环上某顶点的路径,将环绕行 次,再沿一条路径走到接受状态。环的标号长度为正,所以 对应的被接受单词长度互不相同,语言因此是无穷的。反之,长度至少为 的被接受单词,其运行过程(包括初始状态)访问 个状态。由鸽巢原理,其中有两个被访问的状态相同。选择运行过程中首次重复的状态,从其先前出现处到这次重复之间的转移构成接受路径上的非空环,且内部没有重复状态。若语言是无穷的,则存在长度至少为 的被接受单词,因为在有限字母表上,长度更小的单词只有有限多个。这就证明了逆命题以及有限语言的长度界。
证明透视
环必须是有用的
一个可达的环可以被重复,但仅凭这一点并不能得到被接受的单词。证明依次用到三个部分:通向环的进入路径、非空的环,以及通向接受状态的离开路径。“有用”正是要求离开路径能从环自身的顶点出发;下面反例中的拒绝陷阱状态就不满足这一点。
还有三项假设在起作用。环必须含有转移:不同重复次数 对应的单词互不相同,因为它们的长度相差环标号正长度的倍数。 的有限性推动逆命题:长度至少为 的接受运行访问 个状态,鸽巢原理迫使某个状态重复;选取首次重复,使环落在接受运行之上,所以由此得到的环自动是有用的。最后,长度界用到字母表的有限性,因为比 短的单词只有有限多个。
例题详解
例题 1.3.6
(含可达环的空语言)
考虑只有一个状态的 DFA,该状态不是接受状态,并在每个字母上都自环。它有一个可达的环,却不接受任何单词。它的环无法共达到接受状态。由于没有接受状态可达,其语言为空,因而是有限的。
例题 1.3.7
(一个最短的区分单词)
比较接受含偶数个 1 的单词的二进制 DFA,与接受以 0 结尾的单词的 DFA。空单词被奇偶性机器接受,却被以 0 结尾的机器拒绝。乘积的初始状态本身已被标记,所以广度优先搜索返回 作为一个最短的区分单词。
例题 1.3.8
(有用环给出无穷多个单词)
在 上,令初始状态在 上自环,在 上转移到一个接受状态,其余任何输入都转入一个拒绝陷阱状态。该语言为 。初始状态处的自环是有用的,因为 转移可到达接受状态,重复该自环便产生无穷多个被接受的单词。
常见错误
反例模式
位于所有接受路径之外的环
一个可达的拒绝陷阱状态永远自环,但从它出发无法到达任何接受状态。重复该自环得到的是无穷多个被拒绝的单词,而不是无穷多个被接受的单词。可共达性是必不可少的。
常见错误
(状态数与图形都不能决定等价性)
两台自动机的状态数可以不同,却识别同一种语言。图形相同或状态数相同都不是等价性的检验方法。例如,在 上接受所有单词的单状态 DFA,与两个状态都是接受状态、并在 上互相转移的双状态 DFA,识别同一种语言 。
常见错误
(很长的被接受单词不代表语言无穷)
有限语言也可以包含很长的单词:长度界取决于具体那个 DFA 的状态数,并且只有在已排除无穷性之后才适用。在 上,取链 ,后接一个拒绝陷阱状态,只有 接受,它只接受 。这台自动机有六个状态,而唯一被接受的单词比六短。
图的搜索
对于空性,从 开始做广度优先搜索,沿着每个已发现状态的每条出边继续。每个状态在首次被发现时标记,并记录其前驱状态与转移标号。若到达某个接受状态,则沿前驱指针回溯到 并将标号反转,便得到一个见证单词。若初始状态本身就是接受状态,则见证单词的长度为零。若搜索结束时没有发现接受状态,则没有任何单词能被接受,因为从初始状态出发的每条转移路径都已被探索。
对于无穷性,先标记从初始状态可达的状态。然后将每条转移边反向,并同时从所有接受状态出发搜索。这次反向搜索所到达的状态,恰好就是在原图中能够到达接受状态的那些状态。只考虑被两次搜索都标记的状态,并检验由它们导出的有向图是否有环。深度优先搜索或强连通分量算法都可以完成这一检验。只含一个顶点的分量仅当它有自环时才含环;含至少两个顶点的分量必含有向环。
如果在该受限图中找到了环,则两次可达性搜索可以提供进入路径与离开路径,环的搜索则提供被重复的片段。它们的标号给出一族具体的无穷多个单词。进入路径与离开路径不必是简单路径,尽管可以选取简单路径。环每重复一次,单词长度就增加该环标号的正长度,所以不同的重复次数不可能对应同一个单词。
例题 1.3.9
(有限语言与无关的环)
在一元字母表 上,令 ,其中 在 上自环,且只有 是接受状态。该语言为 。三个状态都可达,但 无法到达接受状态,所以它的自环不是有用的。既可达又可共达的状态是 ,它们的导出图无环。
乘积机与见证单词的长度
定义 1.3.10
(乘积自动机与被标记的状态对)
设两个 DFA 的状态集为 ,则乘积至多有 个状态,其转移为
对于等价性,当且仅当一个分量接受而另一个分量拒绝时,标记该状态对。乘积本身不必先最小化。不可达的状态对可以忽略,因为没有任何输入能从乘积的初始状态走到它们。
定理 1.3.11
(最短区分单词的长度)
若同一字母表上两个完全 DFA 的语言不同,则存在恰被其中一个接受、长度至多为 的单词,而且对乘积作广度优先搜索会返回一个最短的这类单词。
证明
(删去重复的乘积状态)
若两种语言不同,则一条最短的区分路径绝不会重复某个乘积状态。若重复了,删去该状态两次出现之间的那一段,剩下的带标号路径会以更短的单词到达同一个被标记的终点。因此,最短区分单词的长度至多为 。
这是乘积构造的一个有限界,并不要求枚举不超过该长度的每个单词。广度优先搜索访问的是状态与转移,而不是显式生成所有可能的单词。
同一个乘积图只需改变被标记的状态对,就能支持其他比较。要检验 ,标记第一个分量接受、第二个分量拒绝的状态对。一个可达的被标记状态对就是包含关系的反例。要检验不相交性,标记两个分量都接受的状态对,一个可达的被标记状态对就提供一个公共单词。正确性论证仍然是对两个同时进行的运行做归纳;改变的只是对接受条件的解释,取决于所问的问题。
完全性与字母表
定义在固定字母表上的完全 DFA 的补,可通过交换接受状态与非接受状态得到。完全性很重要:对每个单词,必须恰好有一条以某个状态结束的运行。在部分转移图中,缺失的转移通常被理解为拒绝。仅仅交换接受标记,并不能把这种缺失的运行变成接受,因此可能得到错误的补。应先添加一个拒绝陷阱状态并补全所有缺失的转移,再交换标记。
反例模式
交换标记需要完全 DFA
断言:交换接受状态与非接受状态,总能得到补语言。在 上,取只有一个接受状态 和转移 的部分转移图,它的语言是 。交换标记后没有任何接受状态,新机器什么也不接受,而 的补含有 。应先补全转移图:加入拒绝陷阱状态 ,以及 和 ;交换后 成为唯一的接受状态,机器恰好接受含有 的单词,这正是补语言。
比较自动机时,应指明共同的字母表。若某台机器对该字母表中的某个符号缺少转移,则按需用拒绝陷阱状态将其补全。环境字母表的选择是问题的一部分:补集是指该字母表上所有不属于该语言的单词。如果在一处把某个符号视为字母表之外,而在另一处又把它视为被自动拒绝的输入,就会在没有明说的情况下改变问题本身。
复杂度与证书
命题 1.3.12
(图搜索的运行时间)
对于 个状态、字母表大小为 的完全 DFA,图搜索需要 时间和 个搜索标记,存储输入的转移表以及任何反向边除外。空性需要一次这样的搜索;无穷性需要两次可达性搜索,以及对导出图的一次环检验,每一步都是这个量级。对等价性所作的乘积搜索至多访问 个状态和 条转移。
证明
(状态与转移的计数)
完全转移表有 条带标号的转移。每次搜索在状态首次被发现时标记它,并对每条出边只检查一次,这就给出所述的界。反向图中某个状态可能有很多入边,但边的总数不变。乘积至多有 个状态,每个状态有 个后继,所以乘积搜索满足类似的界;它可以按需生成后继,而不必存储乘积的每条边。
一个最短的被接受单词或区分单词是正面证书,可以通过模拟一台或两台自动机来检验。关于空性或等价性的断言则有不同的证书:从相应初始状态可达的状态集合,连同它不含任何禁止的终点、并且在每个转移下封闭这一事实。可以通过检查所有带标号的出边来验证封闭性。仅仅没能找到短单词,并不足以下结论,除非搜索已经穷尽了有限的可达状态集,或者使用了另一个有根据的界。
无穷性证书由带标号的进入路径、环与离开路径组成。检查它们的端点以及接受状态,便验证了整个无穷族。反过来,没有有用环这一事实,可以用可达且可共达子图的拓扑排序来证明。这些证书使图论证明更加具体,也把一个会终止的算法,与逐个单词检查无穷语言这种含糊其辞的说法区分开来。
总结
图的可达性把语言的空性判定化为有限搜索。乘积自动机把不等价性化为对分歧状态的可达性。带有非空环的接受路径给出无穷多个长度互异的被接受单词,而每条足够长的接受路径都含有这样的环。
练习
快速检查
(某个 DFA 的初始状态是接受状态。它的语言为空吗?请给出见证单词。)
看空单词的运行。
解答 · 答案
不为空。空单词使机器停在接受的初始状态,它就是见证单词。
快速检查
(若两个 DFA 在空单词上的结果不一致,乘积搜索返回什么?)
检查乘积的初始状态。
解答 · 答案
返回空单词:乘积的初始状态本身恰好有一个接受分量,所以不需要任何转移。
快速检查
(为什么可以任意多次绕行一个有用环,而离开路径的出发状态不变?)
环从哪里开始、在哪里结束?
解答 · 答案
环从同一个状态出发并回到该状态。每次绕行之后,离开路径都可以从这同一个状态出发。
快速检查
(一个四状态 DFA 接受一个长度为四的单词。它的语言可能是有限的吗?)
数一数接受运行访问的状态。
解答 · 答案
不可能。该接受运行(连同初始状态)访问五个状态,因此有某个状态重复。其间的非空环是有用的,并且可以重复,从而产生无穷多个被接受的单词。