ε-NFA

ε-边是控制流接线，不是输入。它允许机器先在几个局部组件之间选择入口，或在一个组件完成后跳到下一个组件，而不必发明只用于连接的输入字符。正则表达式的并、连接和星都可以因此逐块翻译：表达式树的结构由 ε-边承担，真正的字母边只负责消费文本。

闭包不是“最多走一次 ε-边”。若 ε-边形成长链或环，机器在读取下一个符号前可能到达整片状态。集合 $E(S)$ 是有限图上的可达闭包，计算时可用 DFS 或 BFS 访问每个状态一次；ε-环不会造成语义上的无限输入步骤，只会让闭包达到一个不再增长的不动点。

ε-边让表示和组合更方便，识别能力仍然不变。其所有隐式控制位置都来自有限集 $Q$，普通 NFA 可以把“读字符前后所有可能的 ε 移动”预先吸收到字符转移和接受集合里。

设已有自动机 $A$ 识别标识符、$B$ 识别十进制整数。要识别二者的并，可以新建初态 $s$，从 $s$ 分别以 ε-边连到 $A$、$B$ 的初态，再把两边原接受态保留。这一构造不要求两个 token 恰好共享某个真实首字符，也不会把人为的“分支选择符”写进输入。

要识别连接 $L(A)L(B)$，可从 $A$ 的每个接受态连 ε-边到 $B$ 的初态，并把最终接受集合改为 $B$ 的接受态。路径何时离开 $A$ 由非确定性选择；若一个字有多种切分，自动机会同时保留这些可能。星号再增加一个同时作为初态和接受态的新状态，并用 ε-边允许进入组件、重复组件或零次退出。这正是 Thompson 构造的局部模板。

消去 ε-边时，可定义普通 NFA

并令 $F^{\prime }=\{q:E(\{q\})\cap F\ne \varnothing \}$。读字长度归纳表明，新机器一步的状态集恰好合并了旧机器“字符前闭包—读字符—字符后闭包”的全部可能，因而语言不变。这给出了 ε-NFA 与 NFA 表达能力等价的直接证明。

最常见的错误有三类：把 $\epsilon$ 当作会消耗一个位置的“空字符”；只在开始时取闭包，而忘记每次字符转移后再取；消边时保留原接受集合，因而漏掉可经 ε-路径到达接受态的状态。三者都会在空字或组件边界上改变语言。

ε-NFA 是经典正则表达式公理库正则表达式Regular expression从空语言、空字与单符号语言出发，经并、连接和 Kleene 星有限构造的语言表达式。编译的自然中间表示，也适合把多个词法规则或协议片段模块化拼装。执行前可以按上式消去 ε-边，或在状态集模拟中实时维护闭包；二者只是把同一批可达性工作放在不同阶段。

确定化时，DFA 初态应取 $E(\{q_0\})$，每次收集字符后继后再取闭包。这样构造出的集合状态已经吸收所有静默控制流，可继续用于补集、乘积和最小化。ε-NFA 与普通 NFA 的等价关系限定在有限字语言的表达能力上，不意味着它们有相同边数或同样方便的局部结构。