an epsilon-transition

Sometimes you want a machine to be ALLOWED to slip from one state to another without consuming any input at all — a free move, like a secret passage in a board game that you may step through without spending a turn. That free move is an epsilon-transition: a transition labelled with the empty string ε (epsilon) rather than a real symbol. The machine may take it spontaneously, at no cost in input.

Formally, an automaton with epsilon-moves (an epsilon-NFA) has, alongside the usual δ(q, a) for symbols a, also δ(q, ε) giving a set of states reachable on the empty string. During a run, the machine may interleave reading-symbol moves with as many epsilon-moves as it likes. The natural way to handle them is the epsilon-closure: before and after reading each real symbol, you expand your current set of possible states by adding every state reachable through chains of epsilon-moves.

Epsilon-transitions are pure convenience — they make machines easy to glue together. To build an automaton for the union of two languages, just add a new start state with epsilon-moves into the start states of both sub-machines; to chain one machine after another, drop an epsilon-move from the first's accept states into the second's start. This is exactly how Thompson's construction turns a regular expression into an automaton. And like all nondeterminism here, epsilon-moves add no power: every epsilon-NFA can be converted to an ordinary NFA and then to a DFA.