DFA–NFA 等价定理

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

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

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

从六态 NFA 算出五个可达子集 ​

固定字母表 $\mathrm{\Sigma }=\{a,b\}$，考虑语言

它允许先读任意多个 $a$，再读恰好一个或两个 $b$。下面的 NFA 把这两个可能性交给不同分支；初态是 $s$，接受集是 $F=\{f,h\}$。本例没有 ε-边，表中的空集表示该分支不能继续。

$p,f$ 负责一个 $b$ 的分支，$q,g,h$ 负责两个 $b$ 的分支。首次读取 $a$ 时，$s$ 同时激活 $p,q$；若首字符就是 $b$，则直接到 $f,g$。读到第一个 $b$ 时，$f$ 已接受，$g$ 仍在等待第二个 $b$，所以集合里无需每个状态都接受。

现在真正执行可达搜索。队列起初只有 $A=\{s\}$，按 $a,b$ 顺序展开：处理 $A$ 发现 $B=\{p,q\}$ 和 $C=\{f,g\}$；处理 $B$ 不产生新集合；处理 $C$ 发现 $E=\varnothing$ 和 $D=\{h\}$；处理 $E,D$ 后不再增加状态。记录每个新集合一次，就得到下表。

例如 $\mathrm{\Delta }(C,b)=\delta (f,b)\cup \delta (g,b)=\varnothing \cup \{h\}=D$。表中十条转移都落在这五行内，且每一行都有到达见证，因此它们恰好是全部可达状态。虽然幂集含 $2^6=64$ 个候选，本次只需生成五个；原图中 $p$ 可达，却不能据此说单元素子集 $\{p\}$ 可达，因为从初态读 $a$ 必然同时激活 $q$。

输入 $aaabb$ 的集合轨迹为

最终接受。对应的一条成功 NFA 路径是 $s,q,q,q,g,h$；另一分支在第二个 $b$ 上消失。若再追加任一字符，前沿变为空集并拒绝。这解释了为什么“中途曾经接受”不能替代最终接受条件。

还可直接按前缀形状检查整张表：空字到 $A$，非空纯 $a$ 串到 $B$，$a^{\ast }b$ 到 $C$，$a^{\ast }bb$ 到 $D$，其余字到 $E$。这五种情形穷尽输入，且恰有中间两个含 $b$ 的合法形状接受，从而验证所得语言正是 $L$。

确定化至此已经完成，但 $A,B$ 的不同集合名称未必表示不同未来行为。最小化公理库有限自动机最小化Finite automaton minimization · DFA minimization删除不可达状态并按全部未来后缀的行为划分状态，构造识别同一语言的唯一最小 DFA。会继续把它们合并；Nerode 证书公理库Myhill–Nerode 定理Myhill–Nerode theorem语言正则当且仅当前缀的不同未来行为只有有限种，其类数恰为最小 DFA 状态数。则证明剩下四种行为确实不能再少。集合构造负责保存全部分支，最小性要另行证明。

空集、成本与指数边界 ​

本例的空集可由 $ba$ 到达，是一个必需的拒绝死状态；删除它后表就不再是总函数。也有空集不可达的情况：在字母表 $\{a\}$ 上，一个接受态的 $a$ 自环识别 $a^{\ast }$，确定化始终停在同一个单元素集合，无需额外制造可达死状态。

设 NFA 有 $n$ 个状态、$k$ 个显式输入字符，实际生成 $R\le 2^n$ 个子集。若一个 $n$ 位集合能放进一个机器字，并预存每个状态、字符的后继位掩码，简单实现扫描每个子集的至多 $n$ 个成员并取按位或，构造时间为 $O(Rkn)$；用期望常数时间的哈希表驻留集合，空间为 $O(kn+R+Rk)$ 个机器字。本例需要计算的是五行十项，而不是先填六十四行。

上述成本依赖集合能放进单个机器字。若需要 $b=\lceil n/W\rceil$ 个字，上述直接实现的一次集合合并、哈希与比较都不再是常数成本，稠密实现的时间界可写为 $O(Rknb)$。完成显式 DFA 表之后，执行一个输入才只需 $O(|w|)$ 次查表；执行成本并未包含确定化的编译工作。

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

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

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

同一集合不变量也能沿树结构归纳：有限树自动机公理库有限树自动机Finite tree automaton · Bottom-up tree automaton · NFTA有限有序树上的状态汇总支持确定化、空性和语言差判定；可达闭包寻找有限运行，按节点数的动态规划构造最小反例树，并区分树与共享DAG的大小。把每个孩子的可能状态集合合并为父集合，从而完成自底向上的确定化。该结论不能直接改成确定性自顶向下识别；后者先分派孩子状态，在“至少有一个 a 叶子”的语言上已有严格限制。

沿无限字运行时，可达子集仍准确表示当前可能位置，却未必保存“同一条运行无限次接受”的历史。Safra确定化公理库Safra 的 Büchi 确定化Safra determinization · Safra tree construction以命名有序树记录非确定Büchi的接受进展，用持续存在且无限变绿的节点构造确定Rabin自动机。的两状态例子在a与b上得到相同子集，长期接受却不同；命名树补入的正是这些跨轮进展信息，而非修正本页有限字集合不变量。

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

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