DFA–NFA 等价定理

非确定性运行在一个时刻可能位于多个状态，确定化便把“这整组可能位置”命名为一个确定状态。每读一个符号，所有候选同时前进，重复位置自动合并。原来藏在路径分叉中的信息没有消失，而是显式搬进了集合状态。

接受集合为何采用“与 $F$ 相交”也由此一目了然：NFA 只要求存在一条成功路径，所以活跃集合中出现任一接受态就足够。若误写成 $S\subseteq F$，就把存在语义改成了所有活跃分支都接受。

定理只承诺存在等价表示，不承诺表示同样简洁。NFA 用一张共享图表示许多候选的组合；DFA 为每个会影响未来的组合准备独立状态。确定化把运行时维护的集合预先编译成表，换来每个字符一次确定跳转，也可能付出指数空间。

考虑识别“以 01 结尾”的 NFA。状态 $q_0$ 在 0、1 上都自环，并在读到 0 时额外前往 $q_1$；$q_1$ 读 1 到接受态 $q_2$。它不断猜测某个 0 是倒数第二个字符。

从 $\{q_0\}$ 出发，确定化只产生三个可达子集：

读 0 时 $A\to B$、$B\to B$、$C\to B$；读 1 时 $A\to A$、$B\to C$、$C\to A$。只有 $C$ 与原接受集相交。集合 $B$ 的含义不是“机器在两个状态中随机选一个”，而是扫描背景的分支与刚猜到候选起点的分支同时活跃。

上界 $2^{|Q|}$ 在最坏情形不可改成多项式。对

NFA 可以在读到某个 1 时猜它是目标位，再数完余下 $n-1$ 个字符；DFA 则必须区分所有长度为 $n$ 的最近后缀，因为其中任意两个不同后缀都能通过适当续写让目标位暴露出来。于是某些 $O(n)$ 状态 NFA 的最小等价 DFA 确需 $2^n$ 级状态。

不是每个子集都会出现，甚至指数上界常常极松。按需搜索可达子集能避免无用状态，却无法回避语言本身确有指数多种未来行为的情形。最小化也只能合并未来行为相同的可达子集，不能突破 Myhill–Nerode 给出的真实下界。

等价定理把 NFA 纳入正则语言公理库正则语言Regular language存在有限状态识别器的有限字语言，也就是只需固定有限种前缀摘要即可判断的语言。的统一定义，使依赖唯一运行的补集、乘积、等价判定和最小化都能先经确定化应用。它也是Kleene 定理公理库Kleene 定理Kleene's theorem经典正则表达式描述的有限字语言恰好是有限自动机能够识别的语言。翻译链的中段：正则表达式先产生 ε-NFA，再由闭包子集构造得到 DFA。

工程实现可以把构造提前或延后。词法分析器生成器通常预先构造可达 DFA 子集以换取固定吞吐；内存敏感的模式匹配器可以用位集实时维护 NFA 状态；混合实现则只在运行遇到新集合时缓存对应转移。三种策略共享同一个集合不变量。