有限自动机逐个符号读入字符串。状态必须记住已读前缀中足够的信息,才能决定任何后续字符串的结果。我们先构造机器,再证明它恰好识别目标语言。
精确定义
定义 6.1.1
(确定有限自动机)
确定有限自动机(DFA)是五元组 : 是有限状态集合, 是字母表, 是全定义的转移函数, 是初始状态, 是接受状态集合。全定义表示每个状态对每个输入符号都有指定转移。
以 表示从 读完整个字符串 后的状态;特别地,空串满足 ,并且 。当且仅当 ,机器接受 。
除非明确加入拒绝陷阱状态及其转移,缺失箭头本身并不是拒绝规则。
追踪两个奇偶位
令 为所有 的个数及 的个数均为偶数的二进制串。使用 四个状态:第一个字母记录 的个数奇偶,第二个记录 的个数奇偶; 为偶数, 为奇数。初始及唯一接受状态均为 。
| 状态 | 读入 0 | 读入 1 |
|---|---|---|
| EE | OE | EO |
| EO | OO | EE |
| OE | EE | OO |
| OO | EO | OE |
例题 6.1.2
(追踪三个串,包括空串)
读入 得 ,因此接受:它有两个 和两个 。读入 则停在 ,因此拒绝: 的个数为偶数,但 只出现一次。空串不读入任何符号,机器仍停在 ,所以被接受:两种符号均出现零次,而零是偶数。
命题 6.1.3
(奇偶机器识别 L)
对每个二进制串 ,状态 的第一个字母记录 中 的个数的奇偶,第二个字母记录 的个数的奇偶。因此,当且仅当 ,机器接受 。
证明
(对串长度作归纳)
当 时,两个个数均为零,即为偶数,而 。假设命题对 成立。依上表,读入 恰好改变状态的第一个字母(、),第二个字母不变;读入 恰好改变第二个字母(、),第一个字母不变。串 比 多一个 , 的个数相同; 的情形类似,所以命题对 成立。由归纳法,命题对每个有限串成立。
唯一接受状态是 ,故机器接受 恰好等价于两个个数均为偶数。这同时证明两个方向:不会错收 以外的串,也不会漏收 内的串。
证明透视
为何不变量必须是整个状态
归纳不能直接对“”这个命题进行。知道 被拒绝,并不能决定 会不会被接受,下面的反例正说明这一点。命题必须加强为完整的奇偶对,而这正是状态所存储的信息。加强之后,接受条件就成为状态的等式 ,一个论证便同时给出两个包含方向。
八个表项只通过两个统一事实进入证明:读入 翻转第一个字母,读入 翻转第二个字母。所以一个归纳步骤便同时涵盖四个状态。 的全定义性在这里是默默使用的,因为 必须对每个串都有定义。若任何一个表项出错,例如 读入 变成 而不是 ,不变量在前缀 就已失效:它有一个 、两个 ,却会停在 而不是 。
同一台机器还有第二种描述。把 分别对应到模 整数的数对 。
概念视角代数
状态是模 2 的和
在这个对应下,读入 即加上 ,读入 即加上 ;逐一核对八个表项即可确认,例如 。因此读完 后,状态是各字母向量之和:
其中 是 在 中出现的次数。加法可交换,所以重排 的字母不会改变状态: 与 到达同一状态。接受条件就是这个和等于零向量。
为何至少需要四个状态
定义 6.1.4
(可区分串)
设 为语言。若存在串 ,使 与 恰有一个属于 ,则称串 与 对 可区分。
命题 6.1.5
(至少需要四个状态)
任何识别 的 DFA 都至少有四个状态。
证明
(四个两两可区分的前缀)
四对奇偶值均可到达:、、、 分别到达 、、、,所以这四个串的奇偶对互不相同。任取其中两个奇偶对不同的串 和 ,依 选择同一后缀 :若 的 个数为奇数就加入一个 ,若 的 个数为奇数就加入一个 。这个后缀使 两位皆为偶数。对 加上相同后缀,翻转的是相同的位,所以 与 仍至少有一位不同,即至少有一位为奇数。因此 与 恰有一个属于 , 与 可区分。
设 为任何识别 的 DFA。若这四个串中有两个到达 的同一状态,则对每个后缀 , 与 也到达同一状态,因而得到相同结果,这与可区分性矛盾。所以四个串到达 的四个不同状态。上面的四状态机器因而最小。这是对所有 的 DFA 的证明,而不只是找不到更小的图。
例题 6.1.6
(区分两个前缀的后缀)
前缀 与 分别到达 与 。前者的 个数为奇数,所以取 。于是 有两个 、没有 ,属于 ;而 有一个 ,不属于 。若有机器把这两个前缀合并, 与 就会得到相同结果,这是错的。
反例模式
相同结果不代表可以合并
假设有人声称:只要两个前缀都被拒绝,它们就可以共用一个状态。前缀 与 都被拒绝,因为各自有一个个数为奇数。可是接上 后,,而 (一个 和一个 )。两个前缀对这个后续串的表现不同,所以正确的机器必须把它们分开。两个前缀只有在每个后续串都得到相同结果时,才能共用一个状态。
例题 6.1.7
(同一论证用于另一个不变量)
令 为 的个数能被 整除的二进制串。取状态 ( 的个数模 ),读入 则加一(模 ),读入 则不变,初始状态为 ,接受集合为 ;由相同的归纳可知这台机器识别 。前缀 、、 两两可区分。后缀 把 与其余两个分开: 有三个 ,属于 ,而 有四个、 有五个。后缀 把 与 分开: 有三个 , 则有四个。因此至少需要三个状态,而上述机器表明三个已经足够。空串被接受,因为零能被 整除。
常见错误
(状态不等于最后一个符号)
表示目前 的总数为偶数、 的总数为奇数,并不表示最后读到哪个符号。 和 等不同前缀可到达同一状态,因为接上任何相同后缀时,它们的接受结果一致。
常见错误
(长度为偶数并不够)
长度为偶数的串不一定属于 。串 长度为二,但它有一个 和一个 ,两个个数都是奇数。只记住长度奇偶的机器会把 与 合并,无法分辨 和 ,但只有 属于 。
练习
快速检查
(追踪 和 ;哪些被接受?)
逐个符号照着转移表走。
解答 · 答案
依次经过 ,故接受; 依次经过 ,停在 ,故拒绝。
快速检查
(哪个后缀可区分 和 ?请用两个结果串是否被接受来解释。)
试试最短的后缀。
解答 · 答案
后缀 使 到 ,而 到 ;只有前者接受。
快速检查
(若只把接受集合改为 ,转移不变,新语言是什么?)
先看状态的第一个字母代表什么。
解答 · 答案
第一位必须为偶,第二位不限;即所有含偶数个 的二进制串。