动机
有限状态机一次读入一个符号,并且只能记住有界的信息量。这一限制使它所识别的语言类在数学上十分整洁,同时也划出了一条边界:一些看上去很简单的语言需要无界的记忆。本节把这两方面都精确化。我们证明三种不同的描述——确定型自动机、带静默转移的非确定型自动机,以及正则表达式——定义同一类语言,然后证明一个用来说明某语言不属于该类的工具。
若干标准主题没有处理:例如最小化算法以及最小自动机唯一性的完整理论,下文证明的可区分性界只是该理论的下界部分。
定义
定义 1.2.1
(字母表、字与语言)
字母表 是有限非空的符号集合。 上的字是符号的有限序列; 表示空串, 表示所有字的集合。字 的长度记作 。语言是 的任一子集。语言的连接为 ,并令 ,其中 。
语言 (不含任何字)与 (恰含空串)是不同的;在连接与星号的构造中混淆二者是常见的错误来源。
定义 1.2.2
(DFA)
确定型有限自动机是 ,其中 有限, 是全函数,,。定义 与 。则 。
定义 1.2.3
(带静默移动的 NFA)
-NFA 是 ,其中 。对 ,-闭包 是包含 、且包含从任一成员经 -转移可达的所有状态的最小集合。令 ,。语言为 。
概念视角算法
把非确定性看作模拟一个状态集合
可以把 -NFA 看作一个程序,它维护"当前可能所处的状态集合"。每读入一个符号,先把每个成员沿匹配的边移动,再对静默移动取闭包。该程序可能的内存内容只有有限多种,即各个子集,因此它是一台 DFA。指数界是这个程序所需内存的上界;许多 NFA 可达的子集远少于此,如下面第一个例题所示,八个子集中只有四个可达。
定义 1.2.4
(正则表达式)
上的正则表达式由原子 、 以及每个 ,经并 、连接 与星号 构成。其语言为 ,,,,,。表达式的规模把每个原子和每个运算符的出现各计一次。若一个语言等于某个 DFA 的 ,则称其为正则语言。
定义 1.2.5
(可区分的字)
固定语言 。若存在字 使得 与 中恰有一个属于 ,则称字 被 区分。
定理
定理 1.2.6
(子集构造)
设 是状态集为 的 -NFA。定义 ,其中 ,。则 。特别地,-NFA 的每个语言都是正则的,且至多 个状态的 DFA 就足够。
证明
(追踪可达状态的集合)
首先说明 的含义符合直觉: 当且仅当存在一条从 到 的路径,其标记为符号或 ,删去 后拼成 。对 ,这样的路径只用静默移动,得到 。对 ,路径分解为:一段拼成 且终于某个 的路径,一步 -转移到 ,以及一段从 到 的静默路径;归纳假设给出 ,所以 属于所述闭包,反向则按同一分解逆读即可。其次,对 归纳可得 :基础情形就是起始状态的定义,归纳步骤即等式 。 接受意味着 ,即 。
证明透视
子集构造中各个假设在何处起作用
构造只用到 的有限性,使 成为合法的有限状态集。 是全函数,因为 对每个集合(包括空集)都有定义,空集成为陷阱状态。关键一步是等式 :它说明 NFA 的全部非确定性历史被一个集合概括,因此未来只依赖于该集合。证明最后落在 的定义上,即"存在一个成员是接受状态"。
定理 1.2.7
(Thompson 构造)
对每个正则表达式 ,存在 -NFA ,使 ,且它有唯一的起始状态(无入边)、唯一的接受状态(与起始状态不同,无出边),状态数至多为 。
证明
(对表达式结构归纳)
对 的结构归纳。对原子,用两个状态: 不连边, 用 -边相连,字母则用该字母相连;状态数为 ,与规模 相符。对 ,新增起始状态,用 -边指向两个子机的起始状态;新增接受状态,接收来自两个子机接受状态的 -边;状态数 。对 ,从 的接受状态向 的起始状态添加一条 -边;新机的起始与接受状态分别是 的起始状态和 的接受状态。对 ,新增起始状态 与接受状态 ,并添加 -边 、、 与 。"无入边、无出边"的性质可逐项检查得到保持。正确性依赖这些性质:路径只能在子机的起始状态进入、只能从其接受状态离开,所以每条接受路径都分解为对子机的完整穿越。并的路径恰走一个分支;连接的路径先穿越 再穿越 ,得到 ;星号的路径作 次完整穿越,得到 ,直接边 提供 。
定理 1.2.8
(状态消去递推式)
设 是无 -移动的 NFA,状态编号为 ,起始状态为 。令 为所有从 到 、且中间状态都属于 的路径所标记的字的集合。则 ,且
因此 ,是有限多个可由正则表达式给出的语言之并。
证明
(在主元状态的各次出现处切开路径)
基础情形是一步路径的定义,当 时空路径贡献 。对 ,考虑从 到 、中间状态属于 的路径。若 从未作为中间状态出现,则其字属于 。否则,在 作为中间状态的第一次与最后一次出现处切开,并在二者之间的每次出现处也切开。首段从 到 ,中间各段从 到 ,末段从 到 ,每段的中间状态都属于 。这给出第二项;反之,把这样的各段连接起来得到符合要求的路径。该递推式只证明正确性;所得表达式可能增长得非常快。
证明思路
定理 1.2.9
(正则语言的封闭性)
若 是正则语言,则 、 与 也是正则语言。
证明
(补、积与并)
对补集,取 为全函数的 DFA,交换接受与非接受状态:每个字决定唯一的运行,所以它终于 当且仅当不终于 。对 与 的交集,在 上并行运行两台机器,接受集为 ;对字归纳可知配对运行就是两个运行的配对。并集可取至少有一个分量接受的状态对,或用德摩根(De Morgan)律。
定理 1.2.10
(正则语言的泵引理)
设 是正则语言。则存在 ,使每个满足 的 都可写成 ,其中 ,,且对所有 有 。
证明
(对运行用鸽巢原理)
取 的 个状态的 DFA,以及 满足 。其运行的前 个状态 不可能两两不同,故存在 使 。令 为前 个符号, 为接着的 个符号, 为其余部分。则 ,并且从 读入 又回到 ,所以读入 ()也终于 。因此 的终止状态与 或 相同,从而被接受。
定理 1.2.11
(可区分性下界)
若 两两被 区分,则识别 的每个 DFA 至少有 个状态。
证明
(相同状态必给出相同结果)
设 是 的 DFA。若对 有 ,则对每个 ,字 与 终于同一状态,要么都被接受要么都被拒绝,这与可区分性矛盾。故 个状态 互不相同。
反例模式
泵引理的条件是必要的,而非充分的
断言(错误):若一个语言满足泵引理的结论,则它是正则的。令 ,取 。 中长度至少为 的字以 、 或 开头;令 为首字母,。若字以 或 开头,则 变成 或 ,对所有 仍在第二部分中。若字为 ,则泵送给出 :当 时属于第一部分,当 时得到 ,属于第二部分。所以结论对 成立。然而 不是正则的:字 ()两两可区分,因为 ,而当 时 。由可区分性下界,不存在有限 DFA。修正:泵引理只有在其结论失败时才能证明非正则;需要双向检验时应使用可区分性。
例题
例题 1.2.12
(“倒数第二个符号是 1”的子集构造)
设 的状态为 ,起始状态为 ,接受集为 ,边为 、、。从 出发:读 留在 ,读 到 。从 :读 到 ,读 到 。从 :读 到 ,读 到 。从 :读 到 ,读 到 。八个子集中有四个可达,含 的两个是接受状态。一个字被接受当且仅当其倒数第二个符号是 ,因为恰在读到 时进入 ,再读一个符号后到达 。
例题 1.2.13
(“ 的个数为偶数”的状态消去)
在 上,令状态 (起始且接受)表示迄今 的个数为偶数,状态 表示为奇数,读 交换状态,读 留在原状态。则 ,,,。可算得 ,,,,于是 ,这里 表示语言相等。它描述了该语言,并且等于 ,后者是去掉状态 、改写状态 上的环得到的表达式。两种形式相等是通过共同的自动机验证的,而不是靠符号操作。
例题 1.2.14
(素数长度的语言不是正则的)
令 ,并假设存在泵长度 。取素数 ,令 。则 ,。取 泵送:新长度为 ,是两个不小于 的整数之积,因而是合数,所以 ,与引理矛盾。 的选取依赖于 是合法的,因为引理对所有 都成立。
例题 1.2.15
( 有无穷多个两两可区分的字)
对 ,字 两两可区分:取 ,则 ,而当 时 。所以对每个 ,识别 的任一 DFA 至少需要 个状态,这对有限机器是不可能的,故 不是正则的。
反例模式
一个失败的分解并不足够
在 中,可用有效泵长度 :任何长度至少四的字都可泵送其第一个符号。字 也有合法分解 、、。泵送两次得到 ,不在 。但 是正则的:引理只要求存在一个合适分解,并不要求这个自行选取的分解成功。例如选初始零区块中的 ,便可为此字构造有效循环。
例题 1.2.16
(一元平方长度语言不是正则的)
令 。假设其泵长度为 ,选 ,其长度至少为 。任何合法分解都有 ,其中 。取 ,新长度为 。
由于 ,
相邻平方数之间没有整数平方,因此 。这对每个合法分解都矛盾,即使我们不知道分解的具体位置也成立。
常见错误
常见错误
(交换标记不能求 NFA 的补)
交换 NFA 的接受与非接受状态并不能得到其语言的补集;这只对完全 DFA 成立,因为 NFA 可能沿一条路径接受某字而沿另一条路径拒绝它。
常见错误
(空语言不是空串)
把 当作 会使星号的结论出错:,而 与任何语言连接都是空集。
常见错误
(泵引理的分解不是由你选的)
在泵引理的论证中,引理给你 与分解,分解不是由你选的。有效的证明必须处理所有满足 且 的 。你只有两步自由选择:用 表示 ,以及选取 。最后,如上面的反例所示,泵引理不能用来证明某个语言是正则的。
另一个错误是把 当作实际得到的 DFA 的规模。它只是所有可达子集数的上界;不过指数级增长一般无法避免:"倒数第 个符号"的练习给出一个有 个状态的 NFA,而任何对应的 DFA 都至少需要 个状态。
总结
DFA、-NFA 与正则表达式定义同一类语言:子集构造把非确定性化为确定性,Thompson 构造把表达式化为自动机,消去递推式把自动机化为表达式。该类对补、交、并封闭。泵送给出正则语言的一个必要性质,可区分的字则给出状态数的定量下界。最小化算法以及按等价类的完整刻画不在本节范围内。
练习
快速检查
(用泵引理证明 不是正则的。)
选一个前 个符号固定了被泵部分的字。
解答 · 答案
设 为泵长度,取 。任一分解都有 ,所以 ,。则 中 比 多,不属于该语言,矛盾。
快速检查
(给出一个 NFA ,使得交换其接受与非接受状态所得的 NFA 并不接受 的补集。)
试试只有两个状态、一元字母表的 NFA。
解答 · 答案
取状态 ,起始状态 ,接受集 ,字母表 ,边 与 。则 ,其补集为 。交换后接受集为 :字 到达 因而被接受,尽管 。所以新 NFA 接受整个 ,而不是 。
快速检查
(对 ,令 为 上长度至少为 、且倒数第 个符号为 的字的集合。证明识别 的每个 DFA 至少有 个状态。)
比较两个长度为 的字,看它们第一个不同的位置。
解答 · 答案
取全部 个长度为 的字。若 在从左数第 位首次不同,附加 。则 与 的第 位分别是 与 (长度 )的倒数第 个符号,且二者中恰有一个为 。所以 可区分,由可区分性下界得结论。
快速检查
(用 NFA 证明正则语言 的反转 是正则的。)
把 DFA 的每条边反向。
解答 · 答案
设 是 的 DFA,把它看作只有一个起始状态、接受集为 的 NFA。反转每条边,令旧起始状态成为唯一接受状态,并新增一个起始状态,用 -边指向 的每个成员。 中从 到某个 且标记为 的路径,恰对应新机器中从 到 且标记为 的路径。所以新的 -NFA 接受 当且仅当 ,由子集构造知 是正则的。若 ,新机器没有接受路径,而 确实如此。