形式陈述

对 NFA $N=(Q,\Sigma,\delta,q_0,F)$$N=(Q,\mathrm{\Sigma },\delta ,q_0,F)$，构造 DFA

$$ D=(\mathcal P(Q),\Sigma,\Delta,\{q_0\},F_D), $$$$D=(\mathcal{P}(Q),\mathrm{\Sigma },\mathrm{\Delta },\{q_0\},F_D),$$

其中

$$ \Delta(S,a)=\bigcup_{q\in S}\delta(q,a), \qquad F_D=\{S\subseteq Q:S\cap F\ne\varnothing\}. $$$$\mathrm{\Delta }(S,a)=\bigcup _{q\in S}\delta (q,a),F_D=\{S\subseteq Q:S\cap F\ne \varnothing \}.$$

对每个字 $w$$w$，DFA 读完 $w$$w$ 后的状态恰为 NFA 从 $q_0$$q_0$ 读完 $w$$w$ 后可达状态的集合，因此 $L(D)=L(N)$$L(D)=L(N)$。若输入是 $\varepsilon$$\epsilon$-NFA，则先消去空转移，或把初态与每次转移分别改为相应的 $\varepsilon$$\epsilon$-闭包。

直觉

DFA 的一个状态记录 NFA 在读完当前前缀后“所有可能所在状态”的集合。确定性机器不选择分支，而是把全部分支压缩成一个幂集状态同步更新。

例子与边界

若 NFA 有 $n$$n$ 个状态，完整构造至多有 $2^n$$2^n$ 个子集状态，实际只需保留从 $\{q_0\}$$\{q_0\}$ 可达的部分。存在语言族使等价最小 DFA 确实需要指数多状态，所以表达能力相同不表示描述长度相同。空集是合法 DFA 状态，表示所有 NFA 分支均已死亡；不能因其不接受就从转移系统中随意删除。对 $\varepsilon$$\epsilon$-NFA 若忘记闭包，会漏掉不消耗输入即可到达的分支。

推论与应用

该定理说明非确定性不会扩大有限自动机可识别的语言类，却可显著提高表示简洁性。子集构造用于词法分析器、正则表达式引擎、模型检查和 DFA 最小化前处理。

参考资料

• John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed., Pearson, 2006，§2.3。
• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013，§1.2。