NFA：同时身处一群 state
nondeterministic finite automaton 放宽了 DFA 的两条限制：(1) 同一个（state，字符）可以有多个去向，甚至一个都没有；(2) 多了一种 ε-transition——不读任何字符就能转移到另一个 state。于是「机器现在在哪」不再是一个 state，而是同时处于一组 state。
怎么运行一台 NFA?用 subset simulation：始终维护「此刻所有可能所处的 state 集合」。每读一个字符 c，做两件事——move：集合里每个 state 沿 c 边走一步，结果取并集；ε-closure：再把「沿 ε 边可达」的 state 全部并入。起步时集合 =
ε-closure({start})。读完，只要集合里包含任一
accept state 就 ACCEPT——相当于「存在一条成功路径」。
NFA 与 DFA 表达能力相同——NFA 只是更易书写。任何 NFA 都有一台接受同一种语言的 DFA（subset construction 一页就是把这里的「集合」直接变成 DFA 的 state）。NFA 的价值在表达：它和 regex 几乎一一对应，所以编译 regex 时先落成 NFA 最自然（见 Thompson construction 一页）。
留意 (a|b)*abb 这台机器的「分叉」：s0 读到 a 时既能留在 s0（假设这个 a 不是 abb 的开头），又能跳到 s1（假设它是）。NFA 不必当场抉择——两个分支同时保留，集合里于是常常同时有 s0 和后面的 state。读完只要集合包含
accept，就说明至少有一条分支成功。