形式陈述

$\varepsilon$$\epsilon$-NFA 是五元组 $N=(Q,\Sigma,\delta,q_0,F)$$N=(Q,\mathrm{\Sigma },\delta ,q_0,F)$：$Q$$Q$ 是有限状态集，$\Sigma$$\mathrm{\Sigma }$ 是有限输入字母表，$q_0\in Q$$q_0\in Q$，$F\subseteq Q$$F\subseteq Q$，并约定空字记号 $\varepsilon\notin\Sigma$$\epsilon \notin \mathrm{\Sigma }$；转移函数为

$$ \delta:Q\times(\Sigma\cup\{\varepsilon\})\to\mathcal P(Q). $$$$\delta :Q\times (\mathrm{\Sigma }\cup \{\epsilon \})\to \mathcal{P}(Q).$$

标记 $\varepsilon$$\epsilon$ 的转移不消耗输入。状态集 $S$$S$ 的 $\varepsilon$$\epsilon$-闭包 $E(S)$$E(S)$ 是从 $S$$S$ 出发只走零条或多条 $\varepsilon$$\epsilon$ 边可达的全部状态。读字 $w=a_1\cdots a_n$$w=a_1\cdots a_n$ 时，从 $E(\{q_0\})$$E(\{q_0\})$ 开始，反复执行

$$ S_i=E\!\left(\bigcup_{q\in S_{i-1}}\delta(q,a_i)\right), $$$$S_i=E(\bigcup _{q\in S_{i-1}}\delta (q,a_i)),$$

若 $S_n\cap F\ne\varnothing$$S_n\cap F\ne \varnothing$ 则接受。每个 $\varepsilon$$\epsilon$-NFA 都可消去 $\varepsilon$$\epsilon$ 转移得到等价 NFA，也可直接用带闭包的子集构造确定化。

直觉

$\varepsilon$$\epsilon$ 边允许自动机在读入下一个符号前自由重排控制状态，便于把多个小自动机像电路模块一样拼接。

例子与边界

Thompson 构造用 $\varepsilon$$\epsilon$ 边实现正则表达式的并、连接和星号。$\varepsilon$$\epsilon$ 是空字的记号，不是输入字母；走一条 $\varepsilon$$\epsilon$ 边与读取某个“空字符”不同。闭包必须允许零步，所以 $S\subseteq E(S)$$S\subseteq E(S)$，并需反复传递直到不再新增状态。允许 $\varepsilon$$\epsilon$ 转移不会增加可识别语言类，只提高构造便利性；但若遗漏每次读符号后的闭包，确定化会得到错误语言。

推论与应用

$\varepsilon$$\epsilon$-NFA 是正则表达式编译、自动机组合和模型检查中的中间表示；将其与不含 $\varepsilon$$\epsilon$ 边的 NFA 分开，可使每种子集构造的初态和转移公式保持清晰。

参考资料

• John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed., Pearson, 2006，§2.5, finite automata with epsilon-transitions。
• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013，§1.2, nondeterminism and epsilon transitions。