DFA / NFA · subset construction

NFA、DFA 与子集构造

「KMP」一页结尾提到：KMP 的 dfa[c][j] 其实就是一台 DFA。本页以子串匹配这个最熟悉的场景，说明 NFA 是什么、它和 DFA 的差别、以及如何从 NFA 构造出 DFA；结论是：KMP 的那张 DFA，正是「子串匹配 NFA」做子集构造的产物。

DFA（确定有限自动机）：每个（state，字符）恰好一个去向，读一个串毫无悬念地走一条路。

NFA（非确定有限自动机）：同一个（state，字符）可以有多个去向（甚至零个）。它不必当场抉择——所有可能同时保留，于是「现在在哪」不是一个 state，而是一组 state。

两者表达能力完全一样（识别同一类语言），但 NFA 更好「写」、DFA 更好「跑」。桥梁就是子集构造 (subset construction)。

1 · 子串匹配的 NFA：并行尝试所有匹配起点

要判断 text 里是否出现 pattern，可以造一台极简 NFA：状态 $q0\dots q_m$ 排成一条链， $q_j$ 读到 pattern[j] 就前进到 $q_{j+1}$ ; $q_m$ 是接受态（凑齐整个 pattern）。关键在起点 q0 上挂一个「任意字符」的自环——它表示「匹配起点可以是 text 接下来的任意位置」。

非确定性正出在这里： 在 q0 读到 pattern[0] 时，机器有两条路——走自环留在 q0（假设这个字符不是某次匹配的开头），或前进到 q1（假设匹配从这里开始）。NFA 不必二选一，两条都保留。于是运行时始终维护一个活跃 state 集合；只要 $q_m$ 一旦进入这个集合，就说明至少有一条路径完成了匹配 → 命中。

2 · 第一步：跑这台 NFA（子集模拟）

点「下一步」逐字符喂 text。亮起来的圆圈就是当前活跃集合:q0 因为自环永远亮，其余 $q_j$ 亮 ⟺「pattern 的前 j 个字符恰好是已读 text 的一个后缀」。留意右下：活跃集合里最大的那个下标，正好等于 KMP 此刻的状态 j。

活跃集合的「最大元 = KMP 状态」的原因： 两边算的是同一件事：活跃的 $q_j$ 对应「pattern[0..j-1] 是已读 text 的后缀」；其中最长的那个，就是 KMP 维护的「已匹配前缀长度 j」。集合里其余较小的下标，恰好是它的各级 border（最长相等前后缀）——也就是 KMP 失配时会回退到的那些位置。

3 · 第二步：NFA → DFA（子集构造），得到的正是 KMP 那张表

子集构造的想法很直接：既然运行 NFA 时出现的每一种活跃集合都对应一种确定处境，那就把每一个这样的集合各当成一个 DFA 状态。非确定性就此被「打包」消化掉，转移重新变回唯一。对子串匹配 NFA 来说，可达的活跃集合恰好和它的最大元一一对应——于是 DFA 状态正好是 ${0\dots m}$ ，转移表就是 KMP 的 dfa[c][j]。

小结： pattern 是最简单的一种正则，它天然对应一台子串匹配 NFA；对它做子集构造就得到一台 DFA；而这台 DFA（把每个活跃集合按最大元编号后）正是 KMP 的转移表。这也解释了「KMP」那页里那条 X = dfa[pat[j]][X] 的「重启状态」——它就是在追踪「失配后活跃集合里第二大的那条 border 链」。

更一般的 NFA（带 ε 边）、正则编译成 NFA(Thompson)、子集构造的逐步动画、以及 DFA 最小化，见姊妹系列有限自动机科普——本页是它在「字符串匹配」场景下的特例。