在奇偶性例子中,一个 DFA 状态概括已读取的前缀。非确定性自动机在读取相同前缀后,却可能处于多个状态。因此,有用的确定性摘要是一个可能状态的集合,而不是猜哪条路径会成功。改变状态所记住的信息,就自然得到子集构造。
以下始终分清三件事:NFA 内的一条路径、全部可能终点的集合,以及代表这个集合的一个 DFA 状态。这样可以避免两个常见错误:因为某个分支失败便拒绝串,或只因较早的前缀被接受便接受整个串。
模拟前先定义接受条件
定义 6.2.1
(允许空转移的 NFA)
-NFA 是五元组 ,其中 是有限状态集, 是有限输入字母表, 是起点, 是接受状态集,而转移函数为
这里 是 的全部子集所组成的集合。一次转移可以没有目的地、只有一个,或有多个。-转移改变状态但不消耗输入符号; 不是输入字母表中的符号。不含 -转移的普通 NFA,是每个 -后继集合都为空的特例。
一条有限运行路径,把边标签中的 删去后,便拼成所读取的输入串。当至少一条这样的路径由 出发、消耗整个串并在 内结束,机器就接受该串。其他运行可以失败,或在 外结束。这个定义没有概率或随机选择。
下方转移表用空后继集合 表示没有相应边。这与省略 DFA 转移不同:对正在读取的符号没有后继的 NFA 分支会终止,但其他分支仍可继续。
反例模式
一个分支失败,不代表串被拒绝
令 对 0、1 都有自环,也允许 ,再有 ,只有 是接受状态,没有其他边。
输入 01 时,运行 在接受集外结束;但 消耗相同串并接受。如果只选第一条运行,便会错误拒绝。正确模拟应在读取 0 后保留两个终点,再收集读取 1 后的全部后继。
这个 NFA 识别以 01 结尾的串。接受路径必须在倒数第二个 0 进入 ,再在最后的 1 进入 ,因为 没有出边。反过来,任何前缀都可先由 的自环读取,再走最后这两条边。
把不消耗输入的可达状态全部纳入
定义 6.2.2
(-闭包)
对于子集 ,其 -闭包 是由 中某个状态出发,沿零条或多条 -边可达的全部状态所组成的集合。零条边的情况很重要,每个种子状态都属于自己的闭包。
闭包运算满足
第一式把种子状态纳入。第二式是因为把两条 -路径接起来,仍是 -路径,所以已闭的集合不会再增加状态。第三式表示没有任何种子状态,就不能到达任何状态。不要混淆 与 :前者是不含符号的串,后者是不含状态的集合。
例题 6.2.3
(-环的可达终点仍是有限集合)
假设 、, 接受,且在 有一条 0 自环。那么 。这个环允许任意长的 -游走,却没有更多不同状态。
工作列表从种子集合出发,沿 -出边前进;只有尚未见过的目的地才加入。每个状态最多加入一次,所以有限 NFA 不会使搜索永远循环。取闭包并不消耗 0 或 1。
这个例子接受空串,因为起点闭包含有 。再读一个 0 会回到同一闭集合,读 1 则得到空集合。因此,其语言是 ,包括空串。接受不需要无限 -游走:由 到 的有限 -边,已足以见证空串被接受。
先消耗一个符号,再取闭包
对于输入符号 ,把所有一条边可达的目的地收集为
如果 已是 -闭的,即 ,下一个完整可能状态集合就是
原来的闭包处理消耗 之前的 -步骤,新闭包则处理之后的 -步骤。因此,只看原始符号转移目的地,可能漏掉一个接受的可能性。
例题 6.2.4
(恰好接受 0 与 01 的机器)
起点为 ,接受集为 ,完整后继表如下:
| 状态 | 读取 0 | 读取 1 | -后继 |
|---|---|---|---|
读取 0 先产生原始集合 。其闭包是 ,因为可以选择走 -边而不消耗任何符号。因此,即使原始目的地不是接受状态,0 仍被接受。由这个闭集合再读取 1,得到 ,所以 01 也被接受。由 无法再消耗另一个符号。
现在追踪较长输入 010:
| 已处理前缀 | 最后一个符号的原始目的地 | 已确定的 -闭集合 | 如果输入在此结束,此前缀会接受吗? |
|---|---|---|---|
| 尚未读取符号 | 否 | ||
0 | 是 | ||
01 | 是 | ||
010 | 否 |
整个输入 010 被拒绝。前面任何一段前缀被接受,都不代表可以忽略剩余输入。接受状态并非要求提早停止计算的指令。
用图追踪上面三个自动机。符号转移步骤中的原始目标只是预览;取 -闭包后才确定新子集。比较前缀的判断与整个字符串的判断。
证明子集是精确摘要
定理 6.2.5
(子集准确追踪所有运行)
设 是 -NFA。对 上的串 ,令 为:由 出发、恰好消耗 的某条运行可以结束的全部状态;符号之前、之间与之后都允许 -步骤。则对每个串 与符号 ,
而且 接受 ,当且仅当 。
证明
(对已消耗符号数作归纳)
对于空串,运行只能使用 -边,所以恰好得到初始闭包。假设 正确。消耗 的任何运行,都有最后一条消耗符号且标为 的边。在这条边之前,运行已消耗 ,并在 某个状态;之后则可沿 -边前进。因此,它的最后状态一定包含在符号转移及闭包的结果内。
反过来,公式产生的每个状态都有见证:先有一条读取 并到达 中某状态的运行,再有一条 -边,最后接一条有限 -路径。三部分构成读取 的合法运行。对串长度作归纳,就同时证明两个包含方向,所以子集是精确答案,而非过度估计。
最后, 接受 ,当且仅当某条读取 的运行在 内结束,即 。存在某条接受运行的条件,于是成为简单的集合交集测试,不必选定一条运行。
证明透视
为何归纳需要两次取闭包
归纳是对 的符号数进行,而不是对运行长度进行。-环使读取同一个串的运行可以任意长,所以运行长度给不出上界。把每条运行在最后一条消耗符号的边处切开,就有上界:切开前的部分消耗的是严格更短的串 。
有三个要点。第一, 按定义已是 -闭的:读取 的任何运行都可再接上更多 -边。因此公式中的闭包只需补上新符号之后的 -步骤;新符号之前的 -步骤早已包含在 内。第二,包含方向 把运行拆开,说明没有漏掉终点;方向 把三段拼成运行,说明没有虚构终点。第三,接受条件对运行作存在量化,所以只有终点集合才重要:两条运行在同一状态结束,往后能读取的内容完全相同。
两次闭包缺一不可。若由 而非 起步,基础情形便不成立:在 -环例子中, 漏掉接受状态 ,空串会被错误拒绝。若符号转移后不取闭包,归纳步骤便不成立:在恰好接受 0 与 01 的机器中,原始目的地 会使 0 被拒绝。 的有限性在这两个等式中并未用到,它只保证每个闭包可计算,而且子集数量有限。
把可达子集变成 DFA 状态
每个可达的 -闭子集,都用作一个 DFA 状态。起点是 ,读取 的转移是 ,子集与 相交便是接受状态。每个子集对每个符号恰好有一个后继子集;即使子集包含多个 NFA 状态,这仍然是确定性的。
常见错误
(接受子集只需与 F 相交)
子集不必包含于 。在恰好接受 0 与 01 的机器中,读取 0 后到达的子集 含有不接受的 ,却必须接受:结束于 的运行就是见证,一个见证已经足够。若要求 ,0 便会被拒绝;正确的测试是 。
用工作列表创建转移表:从初始子集开始,每个已发现子集只处理一次,计算它对每个字母表符号的后继,只有新后继才加入。子集最多有 个,所以构造会终止。这里的相等是集合相等: 与 代表同一个 DFA 状态。
推论 6.2.6
(子集构造保持语言)
令 为这样的 DFA:起点是 ,读取 的转移是 ,接受状态是与 相交的子集,并只保留由起点可达的子集。则 至多有 个状态,而且 。
证明
(读取 w 后的 DFA 状态是 S_w)
上一个定理的两条等式,正是 的起点与转移规则,所以对 作归纳可知,读取 后 处于状态 。 的每个状态都是 的子集,这给出上界 。最后, 接受 当且仅当 ,这正是 接受 的条件。
概念视角代数
子集步骤是布尔矩阵乘积
把集合 写成 0–1 行向量,-边写成布尔矩阵 ,-边写成 ,以 OR 作加法、AND 作乘法。由于经 -边可达的状态,必可用少于 条 -边到达,所以 就是乘以 ,而 就是 。对恰好接受 和 的机器, 是 ,与 相乘得 ,取闭包得 ,即集合 。
例题 6.2.7
(对上述机器作子集构造)
对于接受 0 或 01 的机器,把可达子集命名为
| DFA 状态 | 读取 0 | 读取 1 | 接受? |
|---|---|---|---|
| (起点) | 否 | ||
| 是 | |||
| 是 | |||
| 否 |
空子集是普通的拒绝 DFA 状态:没有运行剩下,而任何符号都不能凭空创建一条运行。它可达时就应纳入,正如此例。相对地,之前识别以 01 结尾串的 NFA,始终保留 这个可能性,其可达子集只有 、、,空子集并不可达。
把这三个子集命名为 、、。各行由 、、 算出,没有其他边:
| DFA 状态 | 读取 0 | 读取 1 | 接受? |
|---|---|---|---|
| (起点) | 否 | ||
| 否 | |||
| 是 |
串 0101 依次经过 而被接受;010 结束于 而被拒绝;空串停留在拒绝的起点 。
常见错误
(DFA 没有 列)
DFA 转移表对 中每个符号各有一列,没有 列。NFA 的 -边已被吸收进定义各个子集的闭包之中,而确定性机器没有不消耗输入的转移。含 列的表所描述的是另一种机器。
子集构造保留语言,却不是最小化算法。指数上界限制的是可能子集数量,并非声称每个 NFA 都能到达每个子集。
反例模式
两个接受子集仍可能需要不同的后续行为
四状态表中的 与 都接受当前前缀,但不能只凭这点合并。后缀 1 把 带到接受的 ,却把 带到拒绝的 。在已接受前缀 0 后加 1,得到接受的 01;在已接受前缀 01 后加相同后缀,却得到拒绝的 011。
状态等价要求对每个后续串都同意,而不只是同意现在是否接受。证明奇偶 DFA 需要不同奇偶状态时,使用的也是这种区分。
直接实现不变量
以下 Python 程序使用状态名称集合。字典中没有的条目,表示空后继集合;输入是 上的串。空串是 Python 的 "",不是字面字符 "ε"。
def epsilon_closure(seeds, epsilon):
seen = set(seeds)
pending = list(seen)
while pending:
state = pending.pop()
for target in epsilon.get(state, ()):
if target not in seen:
seen.add(target)
pending.append(target)
return frozenset(seen)
def step(states, symbol, transitions, epsilon):
targets = {
target
for state in states
for target in transitions.get((state, symbol), ())
}
return epsilon_closure(targets, epsilon)
def accepts(word, start, accepting, transitions, epsilon):
states = epsilon_closure({start}, epsilon)
for symbol in word:
states = step(states, symbol, transitions, epsilon)
return not states.isdisjoint(accepting)
transitions = {("q0", "0"): {"q1"}, ("q1", "1"): {"q2"}}
epsilon = {"q1": {"q2"}}
for word in ["0", "01", "010", ""]:
print(repr(word), accepts(word, "q0", {"q2"}, transitions, epsilon))
布尔输出依次为 True、True、False、False。工作列表的已访问集合,防止无休止地探索 -环。frozenset 提供不可变表示,日后可用来命名 DFA 子集。不必存储每段分支历史:两条运行在相同前缀后到达同一状态,往后可读取什么只取决于该状态,所以保留一次集合成员关系已足够。
程序刻意等符号转移及其闭包都完成,才更新 states。手算时也应把原始目的地与已消耗前缀所对应的确定状态分开标示,否则表格可能声称已消耗一个符号,却仍显示上一段前缀的集合。
练习
快速检查
(先算闭包,再判断空串)
在 -环例子中,计算 与 。空串会被接受吗?环允许无限多条游走,为什么已访问集合仍保证终止?
解答 · 答案
闭包分别是 与 。空串被接受,因为初始闭包含有接受状态 。搜索记录不同状态,而不是完整游走;两个状态各加入一次,之后重访就不会再加入工作列表。
快速检查
(对后缀语言保留全部分支)
对于接受以 01 结尾串的 NFA,追踪 010 的子集。哪些前缀如果在当时结束会被接受?为什么整个串被拒绝?
解答 · 答案
起初为 ,之后依次为 、、。只有前缀 01 有接受终点。010 的最后子集没有 ,所以整个串被拒绝。留在 的分支仍存在,但该状态不接受。
快速检查
(解释只看原始目的地为什么会错误拒绝)
在恰好接受 0 或 01 的 NFA 中,某模拟读取 0 后得到原始目的地 ,因为 而拒绝。它漏了哪项操作?正确的最终接受测试是什么?
解答 · 答案
符号转移后应取 -闭包。它保留 并加入 ,得到 ,与 的交集非空,所以 0 被接受。-边不消耗额外输入符号,即使已没有符号剩下,仍须考虑它。
快速检查
(分清可达性与幂集上界)
三状态的后缀 NFA 最多有八个可能子集。为什么构造所得 DFA 却只有三个可达状态?为什么不应另把空陷阱状态算作可达?最小化会问另一个什么问题?
解答 · 答案
起始子集包含 ,而 对每个符号都有自环,所以每个到达的子集都保留它。转移恰好产生 、、,分别由 、0、01 到达,没有一个为空。上界计算全部子集,包括不可达的。最小化则问:是否有可达 DFA 状态对每个后续串都同意,因此可在不改变语言下视作同一状态?