非确定性有限自动机

NFA 把尚未排除的解释同时保留下来。读到一个可能的模式起点时，可以让一条分支继续扫描普通文本，另一条分支尝试匹配模式；读到一个有多种语法角色的 token 时，也可以先分支，等后续输入提供证据。非确定性因此是一种描述上的延迟选择，而不是随机押注。

把运行想象成一组标记更接近实际模拟：开始只有 $q_0$ 上有标记，每读一个符号，所有标记沿相应边移动，落到同一状态的标记合并。某一步没有任何标记，说明所有候选都已失败；读完后只要接受态上仍有标记便接受。这套集合语义已经穷举所有分支，不需要一台真实机器“猜中”。

紧凑性来自共享。若许多候选具有公共前缀或公共后缀，NFA 可以让路径分叉再汇合，而 DFA 必须把所有当前活跃候选的组合编码进单个状态。共享会节省描述，却没有提供无界存储，因为 $Q$ 的子集总共仍只有有限多个。

要识别日志字节流中是否出现单词 ERROR，可以让初态在所有字符上自环，并在读到 E 时额外分叉到一条依次期待 R、R、O、R 的路径。错误起点的分支会死亡，初态分支继续寻找下一个 E；一旦某条候选走完整个单词，就进入接受自环。这个结构直接表达“存在某个起点使后续五个字符匹配”。

这个例子也揭示接受时刻的边界。如果接受态没有自环，而输入在 ERROR 后还有字符，该成功分支可能再次死亡，最终语言就变成“以 ERROR 结尾”而不是“包含 ERROR”。NFA 的接受条件在输入结束时检查，不能把中途经过接受态自动理解为整字接受。

非确定性不是概率：转移集合没有概率权重，也不存在“高概率接受”。它也不是并发程序的调度语义；多个分支只是一个字的多条证明路径。若把接受条件改成“所有分支都接受”，得到的是 universal 或交替语义，不能继续套用标准 NFA 的闭包和确定化结论。

补集不能靠直接翻转 NFA 的接受态获得。原语义问“是否存在接受分支”，翻转后问的是“是否存在原拒绝分支”，它并不等于“所有原分支都拒绝”。必须先确定化，使每个字只有唯一集合运行，再交换接受与拒绝。

存在真正的指数简洁性。语言

在 $n\ge 1$ 时可以用恰好 $n+1$ 个状态的简单 NFA：机器猜测某个读到的 1 就是目标位置，再精确走完余下 $n-1$ 个符号。DFA 却必须记住最近 $n$ 位的所有可能组合，最坏需要 $2^n$ 个可区分状态。

DFA公理库确定性有限自动机Deterministic finite automaton · DFA以有限状态和总转移函数为每个输入字规定唯一运行的识别模型。既是 NFA 的语法特例，又与 NFA 在有限字识别能力上等价；子集构造公理库DFA–NFA 等价定理DFA–NFA equivalence · Subset construction每个 NFA 都能以当前可能状态集为一个 DFA 状态，从而在有限字上保持语言不变。把当前可能状态集变成确定状态。ε-NFA公理库ε-NFAEpsilon-NFA · NFA with epsilon transitions允许沿不消耗输入的 ε-边改变控制状态、便于组合局部自动机的 NFA。进一步允许无输入转移，适合拼接自动机片段；消去 ε-边后仍得到同一种正则语言。

词法规则合并、模式搜索和正则表达式编译常先生成 NFA，因为局部构造清晰且能共享路径。执行阶段可以逐字符维护状态集，也可以确定化为表驱动 DFA。前者把组合留到运行时，后者把组合预先展开到状态空间，二者之间的选择主要由内存、吞吐和最坏状态数决定。