2.2 NFA、子集构造与最小化：从多条可能路径到唯一状态
本课目标
- 解释 NFA 与
转移的接受语义； - 正确计算
-closure； - 用子集构造把 NFA 转为等价 DFA；
- 理解状态爆炸、按需确定化和 DFA 最小化。
1. NFA 的转移返回状态集合
带
其中：
给定状态和输入符号，结果可以是零个、一个或多个状态。NFA 接受字符串，当且仅当存在一条路径：消耗完整输入并最终到达某个接受状态。
NFA 不是“随机选一条路”。若实现只随便选一个分支，可能错过接受路径。模拟时应维护当前可达状态集合，或先确定化成 DFA。
2. 空闭包不能漏
处理一个输入符号
- 对当前集合做空闭包；
- 沿所有标记为
的边移动； - 对移动结果再做空闭包。
若只在起点计算一次空闭包，会漏掉读取字符后新出现的空转移路径。
3. 一个识别 ab 或 ac 的 NFA
q0 --a--> q1
q1 --b--> q2 (accept)
q1 --c--> q3 (accept)这个例子没有 ab|ac，通常会创建新起点、分支和汇合点，并用
更能体现非确定性的语言是“倒数第二个字符为 a”：
q0 --a/b--> q0
q0 --a--> q1
q1 --a/b--> q2 (accept)读到每个 a 时，NFA 可以继续留在 q0，也可以猜它是倒数第二个字符而进入 q1。只要有一次猜测在输入结束时到达 q2 就接受。
4. 子集构造法
等价 DFA 的一个状态代表 NFA 的一组可能状态。算法如下：
- DFA 起始状态为
-closure ； - 对尚未处理的状态集合
和每个 ，计算 -closure ； - 每个新集合成为一个 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, accepting):
alphabet = tuple(dict.fromkeys(alphabet))
accepting = frozenset(accepting)
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)
dfa_accepting = {states for states in seen if states & accepting}
return dfa_start, transitions, dfa_accepting这里先把有限字母表保存成元组，避免传入生成器后只在第一个状态上遍历成功。输入映射需要描述有限 NFA，符号和状态需可哈希。下面的 Python 3.9+ 例子含空转移环，以及读完 b 或 c 后才能到达的接受状态：
edges = {
("q0", "a"): {"q1"},
("q1", "b"): {"q2"},
("q1", "c"): {"q3"},
}
epsilon_edges = {
"start": {"q0"},
"q0": {"start"},
"q2": {"done"},
"q3": {"done"},
}
start, table, accepting = determinize(
"start", iter("abc"), edges, epsilon_edges, {"done"}
)
def accepts(text):
state = start
for symbol in text:
if symbol not in table[state]:
raise ValueError(f"outside alphabet: {symbol!r}")
state = table[state][symbol]
return state in accepting
for text in ("", "a", "ab", "ac", "abc", "b", "aab"):
assert accepts(text) == (text in {"ab", "ac"})
assert epsilon_closure({"start"}, epsilon_edges) == {"start", "q0"}
print(len(table), len(accepting))应输出 5 2，表示 5 个可达子集、其中 2 个接受。空转移环因访问集合去重而终止。
空集合也是合法的 DFA 状态，通常对应陷阱状态。若省略它，得到的是部分转移表，需要由执行器补充失败语义。
5. 表达能力相同，表示大小不同
NFA 与 DFA 描述的语言类完全相同：都是正则语言。DFA 是 NFA 的特例；任意 NFA 都能通过子集构造得到等价 DFA。
若 NFA 有
可选策略包括：
- 预先构造完整 DFA，运行时每字符一次转移；
- 直接模拟 NFA 状态集合；
- 按需创建并缓存 DFA 状态；
- 对转移表做压缩，换取额外查找成本。
因此“NFA 给人写、DFA 给机器跑”只是入门口号，不是普遍工程事实。像 Thompson NFA 模拟也可以直接执行，并提供可预测的时间上界。
6. DFA 最小化解决什么
确定化后可能出现行为等价的状态。DFA 最小化把无法被任何后缀区分的状态合并。
经典分割细化从接受与非接受两组开始，某组为空时忽略它：
接受状态 | 非接受状态若同一组中的两个状态在某个字符上转移到不同分组，就必须拆开。不断细分，直到分组稳定。Hopcroft 算法能高效完成这一过程。
对固定字母表和语言，完整且可达的最小 DFA 在状态重命名意义下唯一。最小化前通常先删除从起始状态不可达的状态，否则这些状态不影响语言，却会污染结果。
7. 等价验证
要判断两个 DFA 是否识别同一语言，先统一字母表并用陷阱状态补全缺失转移，再构造乘积自动机，搜索是否存在一个状态对：恰好一边接受、另一边拒绝。若这样的可区分状态可达，就能还原出一个反例字符串；若不可达，两台 DFA 等价。
这比随机生成字符串测试更强。随机测试只能发现某些差异，等价算法能给出完整判定。
常见误区
- NFA 在运行时随机选路：正确语义是存在接受路径，实现需保留全部相关可能性。
- 子集构造会产生幂集中的全部状态：只需生成从起点可达的子集，不必提前替永远不会来的状态订座位。
- NFA 一定比 DFA 小：可能更小，也可能大小相近；结论取决于具体语言和表示。
- DFA 状态越少，扫描器一定越快：缓存布局、字符分类和表压缩同样影响实际性能。
练习
- 为“倒数第二个字符为
a”列出子集构造得到的可达 DFA 状态。 - 给一个含
环的 NFA，手算每个状态的空闭包。 - 写一个直接模拟 NFA 的执行器，与本课确定化结果对照检查
ab|ac；增加一个空串应被接受的例子。 - 构造两台等价但状态数不同的 DFA，手工执行分割细化。
小结
NFA 用状态集合表达多条可能路径，子集构造把这份集合变成 DFA 的单一状态。二者能力相同，主要权衡在构造规模、运行成本与内存。最小化进一步合并对所有未来输入行为相同的状态。
下一课从正则表达式出发构造 NFA，同时拆开三件经常混在一起的事：经典正则语言、实际 regex 方言和具体匹配引擎。