Subset construction：把「集合」固化成 DFA state

NFA 页运行 NFA 时始终维护一个「当前可能所处的状态集合」。subset construction（又称 powerset construction）的思路是：既然运行中出现的每一种集合都对应一种确定的处境，那就把每一个这样的集合预先算出来，各当成一个 DFA 状态。非确定性在构造阶段就被完全消除。

1 · worklist 算法

• DFA 的起始状态取集合 $\varepsilon\text{-closure}(\{q_0\})$，其中 $q_0$ 是 NFA 的 start state。
• 取一个尚未处理的 DFA 状态，它是一个 NFA 状态集合 $S$。对每个字符 $c$ 计算 $T = \varepsilon\text{-closure}(\mathrm{move}(S, c))$。
• $T$ 若是首次出现，登记为一个新的 DFA 状态并排队待处理；无论新旧，都连一条 $S \xrightarrow{\ c\ } T$ 的边。
• 重复到没有新集合出现为止。含任一 NFA accept state 的集合即 DFA 的 accept state。

$n$ 个 NFA 状态最多产生 $2^n$ 个 DFA 状态，即子集的个数，powerset 之名由此而来。这是理论上界，实践中绝大多数子集不会出现，真正长出来的往往不多，图 1-1 即是如此。但指数爆炸确有其事：存在一族语言，其最小 DFA 的状态数相对 NFA 呈指数增长，典型例子是「倒数第 $n$ 个字符取某个指定值」这类语言：NFA 只需 $n+1$ 个状态，而 DFA 必须记住最近 $n$ 个字符，状态数不少于 $2^n$。

DFA minimization 页再把这台 DFA 里行为重复的状态合并到最小。