NFA：同时身处一群 state

nondeterministic finite automaton 放宽了 DFA 的两条限制：同一个（状态，字符）可以有多个去向、也可以一个都没有；另外多出一种 ε-transition，不读任何字符就能转移到另一个状态。于是「机器现在在哪」不再是一个状态，而是同时处于一组状态。

1 · 集合模拟

运行一台 NFA 用的是 subset simulation：始终维护当前所有可能所处的状态集合。起步时集合是 $\varepsilon\text{-closure}(\{q_0\})$。每读一个字符 $c$ 做两步，先 move，即集合里每个状态沿 $c$ 边走一步后取并集；再取 $\varepsilon\text{-closure}$，把沿 ε 边可达的状态全部并入。读完时集合只要包含任一 accept state 即接受，即「存在一条成功路径」。

图 1-1 的机器读到第一个 abb 之前的字符时会分叉：在 s0 上它既能留在 s0（假定该字符不是 abb 的开头），又能跳到 s1（假定它是）。NFA 不必当场抉择，两个分支同时保留，集合里因而常同时含有 s0 与其后的状态。读完只要集合包含 accept state，就说明至少有一条分支成功。