2.4 NFA 与 epsilon-NFA
非确定性有限自动机，也就是 NFA，放宽了 DFA 的规则：同一个状态和输入符号不必确定唯一下一状态。NFA 对同一个符号可以有 0 个、1 个或多个转移。它读取输入时，可以在概念上同时探索多条可能路径。
这并不意味着实现必须神奇地猜对路径。我们可以通过维护活跃状态集（active state set）来模拟 NFA。每读入一个输入符号，所有活跃状态共同贡献可能的下一状态。如果至少有一条路径消耗完整输入并停在接受状态，那么 NFA 接受。
接受规则是存在性条件：
如果存在至少一条接受路径读完整个 w，那么 NFA 接受 w。只要另一条路径成功，失败路径就不重要。这是从 DFA 执行模型切换到 NFA 执行模型时最重要的心理变化。
为什么 NFA 有用
NFA 和 DFA 识别同一类语言：正则语言（regular language）。NFA 并不更强大，但它通常更容易构造。正则表达式运算可以自然映射成小 NFA 片段：
- 并（union）产生分支。
- 连接（concatenation）把一个片段连接到另一个片段。
- 克林星号（Kleene star）产生循环和出口。
- 可选片段变成一个跳过该片段的分支。
这种构造风格对词法分析器生成器（lexer generator）非常有用。我们可以先从很多词法单元（token）正则表达式构造 NFA，再把合并后的 NFA 转成 DFA 来进行快速扫描。
子集构造法
把 NFA 转换为 DFA 时，每个 DFA 状态代表一个 NFA 状态集合。DFA 的开始状态是包含 NFA 开始状态的集合；如果存在空转移（epsilon transition），还要加入空闭包。对于每个输入符号，我们计算从集合中任意 NFA 状态出发可能到达的位置，这个结果集合就成为一个 DFA 状态。
对于一个没有空转移的简单 NFA：
DFA state S = {q0, q2}
on symbol a:
move(q0, a) = {q1}
move(q2, a) = {q2, q3}
therefore:
δ_DFA(S, a) = {q1, q2, q3}如果一个 DFA 状态对应的 NFA 状态集合中包含任何接受状态，那么这个 DFA 状态也是接受状态。这样就保留了 NFA 的存在性接受规则：至少一条活跃 NFA 路径已经成功。
对于有 n 个状态的 NFA，子集构造（subset construction）最坏可能产生 2^n 个 DFA 状态。实践中很多子集不可达，最小化也能进一步减少结果。不过，这种潜在爆炸正是词法分析器生成器需要认真做实现工程的原因之一。
空转移
空转移写作 ε，表示在不消耗输入符号的情况下从一个状态移动到另一个状态。带有这种转移的自动机通常称为 ε-NFA。
空转移是很方便的胶水。假设 regex 中有并（union）a | b。Thompson 风格 NFA 可以创建一个新开始状态，用 ε 边分别连接到 a 片段和 b 片段。此时还没有消耗输入；自动机只是打开了可能匹配的分支。对于 r*，ε 边允许自动机进入循环、重复循环，或者完全跳过它。
一个状态的 空闭包（epsilon-closure） 是从该状态出发，沿零条或多条空转移能到达的所有状态集合。它一定包含原状态，因为走零条边也是允许的。
对于状态集合，闭包是各个状态闭包的并集：
ε-closure({A, C}) = ε-closure(A) ∪ ε-closure(C)模拟 epsilon-NFA 时，在消耗输入之前和每次转移之后都必须加入空闭包。否则模拟会漏掉那些免费可达的状态。
非确定性是构造工具
NFA 并不是真的“随机选路”；只要存在一条完整消费输入并到达接受状态的路径就接受。空转移不消费字符，空闭包是免费可达状态集。模拟一步要先闭包、沿匹配边前进、再闭包。
Thompson 构造（construction）对 r|s 新建开始状态，经空转移到两分支，再汇入新的接受状态；连接用空转移接前后；星号添加跳过和重复路线。它机械、可靠，所以构造阶段偏爱 NFA，执行阶段才偏爱 DFA。
常见误解
- epsilon 不是输入字符，不前进光标。
- 多个活跃状态可用位集（bitset）表示；子集构造会提前把集合变为 DFA 状态。