Epsilon Transition

释义 Definition

ε-转移（空转移）：在有限自动机（尤其是 NFA，非确定有限自动机）中，一种不消耗任何输入符号就能从一个状态跳到另一个状态的转移；也可理解为沿着“空字符串 ε”发生的状态变化。（在不同语境下还可能指更广义的“无输入动作的转移”。）

发音 Pronunciation

/psln trnzn/

例句 Examples

This NFA has an epsilon transition from q0 to q1.
这个 NFA 有一条从 q0 到 q1 的 ε-转移。

By computing the epsilon-closure, we can remove epsilon transitions and build an equivalent DFA.
通过计算 ε-闭包，我们可以消除 ε-转移，并构造一个等价的 DFA。

词源 Etymology

epsilon 来自希腊字母 ε（epsilon），在形式语言与自动机理论中常用来表示空字符串（empty string）；transition 来自拉丁语词根，含义为“跨越、转变”。合起来，epsilon transition 就是“沿着 ε（不读取输入）发生的转移”。

文献与作品 Literary Works

Introduction to Automata Theory, Languages, and Computation（Hopcroft, Motwani, Ullman）
Automata and Computability（Dexter C. Kozen）
Introduction to the Theory of Computation（Michael Sipser）
Compilers: Principles, Techniques, and Tools（Aho, Lam, Sethi, Ullman，“龙书”中在正则表达式到 NFA 的构造里常涉及 ε-转移）