Epsilon Transition

释义 Definition

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

发音 Pronunciation

/ˈɛpsɪlɒn trænˈzɪʃən/

例句 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 就是“沿着 ε（不读取输入）发生的转移”。

相关词 Related Words

• Automaton
• Dfa
• Empty String
• Epsilon
• Epsilon-Closure
• Finite Automaton
• Nfa
• Regular Expression
• State
• Transition Function

文献与作品 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 的构造里常涉及 ε-转移）