2.2 NFA、子集构造与最小化：从多条可能路径到唯一状态
编译高塔的守门机面对同一个字符出现了多条可走的边，馆长让阿花把所有可能状态一并记录下来。
馆长在同一个圆圈上画了两条都标着 a 的边，又添了一条不读取字符的虚线。守门机似乎突然可以“猜路”。非确定性并不是神秘算力：它是把一组可能路径保留下来，只要其中一条完整接受，输入就被接受。
本课目标
- 解释 NFA 与 $\varepsilon$ 转移的接受语义；
- 正确计算 $\varepsilon$-closure；
- 用子集构造把 NFA 转为等价 DFA；
- 理解状态爆炸、按需确定化和 DFA 最小化。
1. NFA 的转移返回状态集合
带 $\varepsilon$ 转移的 NFA 可写成：
$$ N=(Q,\Sigma,\delta,q_0,F), $$
其中：
$$ \delta:Q\times(\Sigma\cup{\varepsilon})\to\mathcal{P}(Q). $$
给定状态和输入符号，结果可以是零个、一个或多个状态。NFA 接受字符串，当且仅当存在一条路径：消耗完整输入并最终到达某个接受状态。
NFA 不是“随机选一条路”。若实现只随便选一个分支，可能错过接受路径。模拟时应维护当前可达状态集合，或先确定化成 DFA。
2. 空闭包不能漏
$\varepsilon$-closure$(S)$ 是从状态集合 $S$ 出发，只沿零条或多条 $\varepsilon$ 边能到达的所有状态，也包含 $S$ 自身。
处理一个输入符号 $a$ 的步骤是：
- 对当前集合做空闭包；
- 沿所有标记为 $a$ 的边移动；
- 对移动结果再做空闭包。
若只在起点计算一次空闭包，会漏掉读取字符后新出现的空转移路径。
3. 一个识别 ab 或 ac 的 NFA
q0 --a--> q1
q1 --b--> q2 (accept)
q1 --c--> q3 (accept)这个例子没有 $\varepsilon$ 边，但 q1 对不同字符有不同选择。若用 Thompson 构造表达式 ab|ac，通常会创建新起点、分支和汇合点，并用 $\varepsilon$ 边连接片段。
更能体现非确定性的语言是“倒数第二个字符为 a”：
q0 --a/b--> q0
q0 --a--> q1
q1 --a/b--> q2 (accept)读到每个 a 时，NFA 可以继续留在 q0，也可以猜它是倒数第二个字符而进入 q1。只要有一次猜测在输入结束时到达 q2 就接受。
4. 子集构造法
等价 DFA 的一个状态代表 NFA 的一组可能状态。算法如下：
- DFA 起始状态为 $\varepsilon$-closure$({q_0})$；
- 对尚未处理的状态集合 $S$ 和每个 $a\in\Sigma$，计算 $\varepsilon$-closure$(\operatorname{move}(S,a))$；
- 每个新集合成为一个 DFA 状态；
- 只要集合包含任意 NFA 接受状态，它就是 DFA 接受状态；
- 重复直到不再出现新集合。
from collections import deque
from collections.abc import Mapping, Set
State = str
def epsilon_closure(
states: Set[State], epsilon_edges: Mapping[State, Set[State]]
) -> frozenset[State]:
closure = set(states)
pending = list(states)
while pending:
state = pending.pop()
for target in epsilon_edges.get(state, set()):
if target not in closure:
closure.add(target)
pending.append(target)
return frozenset(closure)
def determinize(start, alphabet, edges, epsilon_edges):
dfa_start = epsilon_closure({start}, epsilon_edges)
pending = deque([dfa_start])
seen = {dfa_start}
transitions = {}
while pending:
current = pending.popleft()
transitions[current] = {}
for symbol in alphabet:
moved = {
target
for state in current
for target in edges.get((state, symbol), set())
}
target = epsilon_closure(moved, epsilon_edges)
transitions[current][symbol] = target
if target not in seen:
seen.add(target)
pending.append(target)
return dfa_start, transitions空集合也是合法的 DFA 状态，通常对应陷阱状态。若省略它，得到的是部分转移表，需要由执行器补充失败语义。
5. 表达能力相同，表示大小不同
NFA 与 DFA 描述的语言类完全相同：都是正则语言。DFA 是 NFA 的特例；任意 NFA 都能通过子集构造得到等价 DFA。
若 NFA 有 $n$ 个状态，子集构造理论上最多产生 $2^n$ 个状态。某些语言确实需要指数级 DFA，但许多具体 NFA 只有少数可达子集。实现通常只创建从起始状态实际可达的集合。
可选策略包括：
- 预先构造完整 DFA，运行时每字符一次转移；
- 直接模拟 NFA 状态集合；
- 按需创建并缓存 DFA 状态；
- 对转移表做压缩，换取额外查找成本。
因此“NFA 给人写、DFA 给机器跑”只是入门口号，不是普遍工程事实。像 Thompson NFA 模拟也可以直接执行，并提供可预测的时间上界。
6. DFA 最小化解决什么
确定化后可能出现行为等价的状态。DFA 最小化把无法被任何后缀区分的状态合并。
经典分割细化从两组开始：
接受状态 | 非接受状态若同一组中的两个状态在某个字符上转移到不同分组，就必须拆开。不断细分，直到分组稳定。Hopcroft 算法能高效完成这一过程。
最小 DFA 在状态重命名意义下唯一。最小化前通常先删除从起始状态不可达的状态，否则这些状态不影响语言，却会污染结果。
7. 等价验证
要判断两个 DFA 是否识别同一语言，可以构造乘积自动机，搜索是否存在一个状态对：恰好一边接受、另一边拒绝。若这样的可区分状态可达，就能还原出一个反例字符串；若不可达，两台 DFA 等价。
这比随机生成字符串测试更强。随机测试只能发现某些差异，等价算法能给出完整判定。
常见误区
- NFA 在运行时随机选路：正确语义是存在接受路径，实现需保留全部相关可能性。
- 子集构造会产生幂集中的全部状态：只需生成从起点可达的子集。
- NFA 一定比 DFA 小：可能更小，也可能大小相近；结论取决于具体语言和表示。
- DFA 状态越少，扫描器一定越快：缓存布局、字符分类和表压缩同样影响实际性能。
练习
- 为“倒数第二个字符为
a”列出子集构造得到的可达 DFA 状态。 - 给一个含 $\varepsilon$ 环的 NFA，手算每个状态的空闭包。
- 在确定化代码中返回接受状态集合，并为
ab|ac编写测试。 - 构造两台等价但状态数不同的 DFA，手工执行分割细化。
小结
NFA 用状态集合表达多条可能路径，子集构造把这份集合变成 DFA 的单一状态。二者能力相同，主要权衡在构造规模、运行成本与内存。最小化进一步合并对所有未来输入行为相同的状态。
下一课从正则表达式出发构造 NFA，同时拆开三件经常混在一起的事：经典正则语言、实际 regex 方言和具体匹配引擎。