epsilontransitions

Epsilon transitions, also called epsilon moves or lambda moves, are transitions in a finite automaton and related computational models that do not consume any input symbol. They are labeled with epsilon (often written as ε). From a given state, an epsilon transition allows the machine to move to another state spontaneously, without advancing the input pointer.

In nondeterministic finite automata (NFAs), epsilon transitions extend the model to epsilon-NFAs. At any step, if the current state has epsilon transitions, the machine may follow them, reaching the epsilon-closure of the current configuration. The epsilon-closure of a state is the set of states reachable through solely epsilon moves, including the original state. The language recognized by an epsilon-NFA is the same as that recognized by some ordinary NFA (one without epsilon transitions); there are standard methods to remove epsilon transitions.

Epsilon transitions facilitate construction techniques such as Thompson’s construction from regular expressions and allow convenient modeling of optional subpatterns and instantaneous state changes. In the standard subset construction for converting NFAs to DFAs, epsilon-closures are used to define the input-move on each DFA state.

In pushdown automata, epsilon transitions permit changing states or manipulating the stack without consuming input, enabling additional nondeterministic behavior and more compact representations. Not all models allow epsilon transitions; their inclusion does not increase the expressive power of finite automata over a fixed alphabet, but they simplify design and analysis. Eliminating epsilon transitions may affect the size of the automaton or the complexity of certain algorithms, but equivalent machines exist.