Epsilon-Moves and the Epsilon-Closure

A move that reads nothing

In the previous guide a nondeterministic finite automaton earned its power by cloning: on a single symbol it could split into several copies, each chasing a different next state, and it accepted if any clone finished in an accept state. The transition there sends a state-plus-symbol to a whole set of states — that is the set-valued transition you already met, written delta(q, a) = {p1, p2, ...}. Now we add one last, almost mischievous, freedom.

An epsilon-move (or epsilon-transition) is an arrow between two states labelled not by a real symbol but by epsilon (ε), the empty string. The machine may slide along that arrow at any time, reading nothing from the input and consuming no character. Think of it as a trapdoor inside the machine: you are standing in state q, you spot a trapdoor labelled ε leading to state p, and you may simply fall through it for free, before, after, or instead of reading the next symbol. An NFA that is allowed such moves is called an epsilon-NFA.

Why bother? Machines that snap together

The payoff for epsilon-moves is gluing. Suppose you have one small machine for the language of strings ending in 'ab' and another for strings made only of c's, and you want a machine for 'either one'. With epsilon-moves you build it in seconds: add a fresh start state and draw two epsilon-arrows, one into each old machine's start. The reader simply guesses, for free, which sub-machine to enter. No symbols are rewritten, no transitions are merged by hand — the empty-string arrows do the wiring.

This is exactly how regular operations are realised mechanically: an epsilon-arrow from the end of machine A to the start of machine B gives concatenation; a loop-back epsilon-arrow gives the Kleene star. You will see this used in earnest when we turn a regular expression into a machine — the standard construction is just a recipe for snapping tiny pieces together with epsilon-arrows. So epsilon-moves are less a new kind of power and more a universal connector, like the studs on a LEGO brick.

The epsilon-closure: everywhere you can drift for free

Once free moves exist, 'which state am I in?' becomes the wrong question. The right question is 'which states could I be in right now without reading anything?' The answer is the epsilon-closure of a state q, often written E(q) or ECLOSE(q): the set of all states reachable from q by following zero or more epsilon-arrows. It always includes q itself (following zero arrows), then everything one ε-hop away, then their ε-neighbours, and so on until nothing new appears.

1. Start a worklist containing just q, and mark q as 'in the closure'.
2. Take any state r off the worklist and look at every epsilon-arrow leaving r.
3. For each state s that arrow leads to: if s is new, add it to the closure and to the worklist; if s was already in, ignore it.
4. Repeat until the worklist is empty. The marked set is E(q) — and it is finite, so this always halts.

This is just a graph search (breadth- or depth-first) over the epsilon-arrows only, and because there are finitely many states it cannot run forever — even a cycle of ε-arrows is harmless, since once a state is marked you never revisit it. To run a string on an epsilon-NFA you alternate two moves: take the epsilon-closure of where you are, then read one real symbol from the whole current set of states, then take the epsilon-closure again. The closure mops up every free drift; the symbol-step is the only thing that advances your finger on the input.

A tiny worked trace

Here is a three-state epsilon-NFA over the alphabet Σ = {a, b}. The start state is q0; the only accept state is q2. State q0 has an epsilon-arrow to q1, and q1 has an epsilon-arrow to q2; the real-symbol arrows are q0 reads a to q0, q1 reads b to q1. Notice that nothing actually reaches q2 by reading a symbol — q2 is only ever reached by drifting along ε-arrows.

States: q0 (start), q1, q2 (accept)

   epsilon            epsilon
q0 ---------> q1 ---------> q2
 |             |
 | a           | b
 v             v
q0            q1            (q2 has no outgoing arrows)

E(q0) = {q0, q1, q2}     <- drift q0 -> q1 -> q2 for free
E(q1) = {q1, q2}
E(q2) = {q2}

Run on input "a":
  start set      = E(q0)        = {q0, q1, q2}
  read 'a'       : q0--a-->q0   (q1,q2 have no 'a' arrow) = {q0}
  closure again  = E(q0)        = {q0, q1, q2}
  end of input. q2 is in the set -> ACCEPT

Trace it slowly and the discipline becomes clear. You never sit in a single state; you sit in a set of states, and that set is always closed under epsilon-moves. The string is accepted exactly when, after the last symbol and one final closure, the set you hold shares at least one state with the accept states. This 'set of states' viewpoint is not a coincidence — it is the seed of the subset construction in a later guide, where each such set becomes a single state of an equivalent deterministic machine.

No new power — only new convenience

It is tempting to think free moves make the machine stronger. They do not. The epsilon-closure is precisely the tool that lets us remove every ε-arrow: replace each symbol-transition delta(q, a) by 'first close, then read a, then close again', and the empty-string arrows vanish into ordinary ones. The result is a plain NFA recognising the very same language. So a DFA, an NFA, and an epsilon-NFA are all equally expressive — this is the equivalence of the three models, and each recognises exactly the regular languages, nothing more.

Hold on to the honest lesson from the last guide: nondeterminism — whether by cloning or by free moves — is a mathematical device for writing machines concisely, not random behaviour and not free parallel hardware. A real CPU cannot fall through trapdoors. When you eventually run an epsilon-NFA on an actual computer, you simulate every branch at once by tracking the whole set of reachable states, which is exactly the closure-then-read loop above. The convenience is for the human designer; the machine still does honest work, and the price will show up as the NFA-to-DFA blowup later.