ε-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 \}$。对非空字作长度归纳，新机器读完后的状态集等于旧机器的闭合前沿：第一步的公式已包含初始闭包，后续每步也吸收字符前后的 ε 移动。空字时，新机器仍停在 $q_0$，而 $q_0\in F^{\prime }$ 恰好等价于 $E(\{q_0\})\cap F\ne \varnothing$。因此两个初始状态集虽然未必相同，接受条件仍对全部字一致。这给出了 ε-NFA 与 NFA 表达能力等价的直接证明。

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

如果原图没有任何 ε-边，则 $E(S)=S$，上述初态、转移和消边接受集都退化为普通 NFA 的定义。六态 NFA 的确定化例子理路DFA–NFA 等价定理DFA–NFA equivalence · Subset construction每个 NFA 都能以当前可能状态集为一个 DFA 状态，从而在有限字上保持语言不变。正属于这种情况：语言表达式 $a^{\ast }b(\epsilon \mid b)$ 中的 $\epsilon$ 表示可以不再追加字符，并不表示图上一定有 ε-边。若为了拼装分支另加 ε-初态，初始闭包和可达集合就要重新计算，不能直接沿用那张无 ε-边的子集表。

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

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

加权 ε 消边理路加权 ε 闭包与消边Weighted epsilon closure · Weighted epsilon removal · 加权 epsilon 消除非负有理权自动机的ε矩阵在谱半径小于一时具有有限闭包；截断路径和证明矩阵消边保持每个字的权值，两态算例揭示重复闭包与发散环的边界。还须累计各条静默路径的贡献。普通数值加法不会像集合并那样消去重复，所以不能直接把字符转移前后的两个布尔闭包都换成数值闭包矩阵；相邻闭包可能为同一条路径引入多个切点。该页用谱条件保证收敛，并逐项算出重复计权反例。