← 有限自动机 · DFA / NFA / regex 与它们之间的转换 / Subset construction：把「集合」固化成 DFA state 待审核 4 / 7
subset construction · NFA → DFA

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

NFA 一页里跑 NFA 时，我们时刻维护一个「当前可能所处的 state 集合」。subset construction（又叫 powerset construction）的思路很直接：既然 NFA 运行中出现的每一种集合都对应一种确定的处境，那就把每一个这样的集合预先算出来，直接当成一个 DFA 的 state。非确定性在构造阶段就被完全消除。

算法 (worklist):

  • DFA 的 start = ε−closure(NFAstart)\varepsilon -closure(NFA start) 这个集合。
  • 取一个还没处理的 DFA state（它是一个 NFA-state 集合 S），对每个字符 c 算 T=ε−closure(move(S,c))T = \varepsilon -closure(move(S, c))。
  • T 若是第一次出现，就登记成一个新 DFA state，排队待处理；并连一条 S --c--> T 的边。
  • 重复直到没有新集合。含任一 NFA accept state 的集合，就是 DFA 的 accept state。

左边是原 NFA（高亮当前在算的集合），右边是 DFA 一格格长出来。

n 个 NFA state, DFA 最多 2ⁿ 个 state（子集个数）——这是理论上界，所以叫 powerset。实践中绝大多数子集根本不会出现，真正长出来的往往不多（本例就几个）。但「指数爆炸」确有其事：某些语言的最小 DFA 必然比 NFA 大指数级。DFA minimization 一页再把这台 DFA 里行为重复的 state 合并到最小。