What is the epsilon-closure of a set of states in a finite automaton, and why does the subset construction need it?

middlemust knowfreq 55%

answer

some edges consume nothing
where you already are, for free
reflexive and transitive, one direction
apply it at start and after each step
cycles are fine; visit each state once

basics

~20 s

The epsilon-closure of a state set is that set plus every state reachable from it by epsilon moves alone. Determinisation needs it because such moves consume no symbol, so those states are already live before the next symbol arrives.

solid answer

~50 s

An epsilon move is a transition a machine may take without consuming an input symbol. That means the honest answer to "where is the machine right now?" is never a single state: it is a set closed under epsilon moves. The epsilon-closure of a set S is S together with every state reachable from a member of S by following epsilon moves only — computed with a simple worklist that pushes each newly discovered state once, so it terminates even with epsilon cycles. The subset construction applies it in exactly two places: to {start} to build the initial subset, and to the union of successors after every symbol step. Skip either and the resulting deterministic machine misses accepting paths. Closure is also why epsilon moves add no recognising power — they can always be eliminated.

An **epsilon move** is a transition a machine may take without consuming an input symbol. That means the honest answer to "where is the machine right now?" is never a single state: it is a set closed under epsilon moves. The **epsilon-closure** of a set `S` is `S` together with every state reachable from a member of `S` by following epsilon moves only — computed with a simple worklist that pushes each newly discovered state once, so it terminates even with epsilon cycles. The subset construction applies it in exactly two places: to `{start}` to build the initial subset, and to the union of successors after every symbol step. Skip either and the resulting deterministic machine misses accepting paths. Closure is also why epsilon moves add no recognising power — they can always be eliminated.

code

pseudocode · 10 lines

pseudocode

function epsilon_closure(S):
    result <- copy of S            // closure is reflexive
    stack  <- all states in S
    while stack is not empty:
        q <- pop(stack)
        for each state r such that q --epsilon--> r:
            if r not in result:
                add r to result    // each state enters at most once,
                push r onto stack  // so epsilon cycles terminate
    return result

go deeper

for a junior

Recall that some transitions consume no input symbol, and that the closure of a set is that set plus everything reachable from it along those free transitions.

for a middle

Give the definition precisely — reflexive, transitive, one-directional — and name both places determinisation applies it: the start subset and every subset produced by a symbol step.

for a senior

Show you can diagnose the failure mode: a missing closure under-accepts silently, so the tests that catch it are the empty string, an epsilon cycle, and closure idempotence.

for a principal

Weigh where the closure cost lands — folded into a table once at build time, or paid per symbol when the machine is simulated directly — and which your latency budget can absorb.

Why epsilon moves exist at all

An epsilon move (also written as a lambda move) is a transition a machine may follow without consuming an input symbol. It is a modelling convenience: it lets you glue machines together end to end, or offer a choice between several sub-machines, without rewriting anybody's transition table. If you are assembling a stream sensor out of one small acceptor per signature, an epsilon fan-out from a single start state into each sub-acceptor is the cheapest possible join.

The price is that "the current state" stops being a well-defined single thing. Before any symbol is read, the machine may already have drifted along epsilon edges. So the honest description of where the machine is, at any moment, is a set of states closed under epsilon moves.

The definition

For a set of states S, the epsilon-closure of S is:

every state in S itself, plus
every state reachable from some member of S by following one or more epsilon moves and nothing else.

Two details matter and are routinely missed:

Closure is reflexive. S is always a subset of its own closure, even when the machine has no epsilon moves at all — in that case the closure is just S.
Closure is transitive and cycle-safe. If p has an epsilon move to q and q has one to r, then r is in the closure of {p}. Epsilon cycles are legal; the worklist below visits each state at most once, so it terminates anyway.

It is directed. r being in the closure of {p} says nothing about p being in the closure of {r}; the arrows only run one way.

Where determinisation uses it

The subset construction turns sets of nondeterministic states into single deterministic states. Epsilon moves enter at exactly two points:

Step	Without epsilon moves	With epsilon moves
Initial state	`{start}`	`closure({start})`
Step on symbol `a` from subset `S`	union of `move(q, a)` for `q` in `S`	`closure(` union of `move(q, a)` `)`
Accepting subsets	subsets containing an accepting state	unchanged — but closure may have put one there
Empty result	the trap subset	still the trap; closure of the empty set is empty

Miss the closure on the start subset and a machine whose start state reaches an accepting state by epsilon moves alone will wrongly reject the empty string. Miss it after a symbol step and you lose every path that slides forward without consuming input — the determinised machine then accepts a strict subset of the original language, which is the classic silent bug in a hand-written converter.

Epsilon moves add no power

Because closure is computable and finite, epsilon moves can always be eliminated: replace each transition by "close, then step, then close", and mark a state accepting if its closure contains an accepting state. The result accepts exactly the same language with no epsilon edges. This is a small instance of the broader result that nondeterminism — in any of its finite-state forms — buys convenience and state economy, not recognising power.

Cost

Computing one closure is a graph reachability search over the epsilon edges only, so it is linear in the number of states plus epsilon edges, and it is done once per subset per symbol during construction. It is not a per-input-symbol cost at match time: once the deterministic table exists, closures have already been folded into it. When the machine is simulated directly rather than determinised, the closure is paid per symbol, which is one of the reasons per-symbol work differs between the two strategies.

Checking your own implementation

Three cheap tests catch almost every closure bug:

Empty input. Feed the empty string. If the start state reaches an accepting state through epsilon moves only, the machine must accept.
Epsilon cycle. Build a machine with an epsilon loop and confirm the closure terminates and contains every state on the loop.
Closure idempotence. Closing an already-closed set must change nothing. If it does, the worklist is dropping states.

## Why epsilon moves exist at all An **epsilon move** (also written as a lambda move) is a transition a machine may follow **without consuming an input symbol**. It is a modelling convenience: it lets you glue machines together end to end, or offer a choice between several sub-machines, without rewriting anybody's transition table. If you are assembling a stream sensor out of one small acceptor per signature, an epsilon fan-out from a single start state into each sub-acceptor is the cheapest possible join. The price is that "the current state" stops being a well-defined single thing. Before any symbol is read, the machine may already have drifted along epsilon edges. So the honest description of where the machine is, at any moment, is a **set of states closed under epsilon moves**. ## The definition For a set of states `S`, the **epsilon-closure** of `S` is: - every state in `S` itself, plus - every state reachable from some member of `S` by following **one or more epsilon moves and nothing else**. Two details matter and are routinely missed: 1. **Closure is reflexive.** `S` is always a subset of its own closure, even when the machine has no epsilon moves at all — in that case the closure is just `S`. 2. **Closure is transitive and cycle-safe.** If `p` has an epsilon move to `q` and `q` has one to `r`, then `r` is in the closure of `{p}`. Epsilon cycles are legal; the worklist below visits each state at most once, so it terminates anyway. It is directed. `r` being in the closure of `{p}` says nothing about `p` being in the closure of `{r}`; the arrows only run one way. ## Where determinisation uses it The subset construction turns sets of nondeterministic states into single deterministic states. Epsilon moves enter at exactly two points: | Step | Without epsilon moves | With epsilon moves | |---|---|---| | Initial state | `{start}` | `closure({start})` | | Step on symbol `a` from subset `S` | union of `move(q, a)` for `q` in `S` | `closure(` union of `move(q, a)` `)` | | Accepting subsets | subsets containing an accepting state | unchanged — but closure may have *put* one there | | Empty result | the trap subset | still the trap; closure of the empty set is empty | Miss the closure on the start subset and a machine whose start state reaches an accepting state by epsilon moves alone will wrongly reject the empty string. Miss it after a symbol step and you lose every path that slides forward without consuming input — the determinised machine then accepts a **strict subset** of the original language, which is the classic silent bug in a hand-written converter. ## Epsilon moves add no power Because closure is computable and finite, epsilon moves can always be eliminated: replace each transition by "close, then step, then close", and mark a state accepting if its closure contains an accepting state. The result accepts exactly the same language with no epsilon edges. This is a small instance of the broader result that nondeterminism — in any of its finite-state forms — buys **convenience and state economy, not recognising power**. ## Cost Computing one closure is a graph reachability search over the epsilon edges only, so it is linear in the number of states plus epsilon edges, and it is done once per subset per symbol during construction. It is not a per-input-symbol cost at match time: once the deterministic table exists, closures have already been folded into it. When the machine is simulated directly rather than determinised, the closure *is* paid per symbol, which is one of the reasons per-symbol work differs between the two strategies. ## Checking your own implementation Three cheap tests catch almost every closure bug: 1. **Empty input.** Feed the empty string. If the start state reaches an accepting state through epsilon moves only, the machine must accept. 2. **Epsilon cycle.** Build a machine with an epsilon loop and confirm the closure terminates and contains every state on the loop. 3. **Closure idempotence.** Closing an already-closed set must change nothing. If it does, the worklist is dropping states.

What goes wrong if a converter closes the start subset but forgets to close after each symbol step?
It loses every path that advances by epsilon moves after consuming a symbol, so subsets are too small and some accepting paths vanish. The determinised machine then accepts a strict subset of the original language — it never over-accepts, which is why the bug tends to survive happy-path tests.
Can the epsilon-closure of a set ever be smaller than the set itself?
No. Closure is reflexive: every member of the input set is in the output. With no epsilon moves the closure equals the input exactly; otherwise it is strictly larger. A closure step that removes states is an implementation bug, not a property of the definition.
How does closure decide whether a subset of the determinised machine is accepting?
A subset is accepting when it contains at least one accepting state of the original machine. Closure matters because it may be what *puts* an accepting state into the subset — a state reachable by epsilon moves alone still counts as live, so the subset accepts.

saying these in an interview costs you the question

Thinks the closure excludes the states you started from
Believes epsilon moves let a finite machine recognise more languages
Computes the closure only once, at the start state
Treats an epsilon move as consuming a blank or padding symbol
Says epsilon cycles make the closure computation loop forever
Follows epsilon edges backwards as well as forwards

What is the epsilon-closure of a set of states in a finite automaton, and why does the subset construction need it?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~3 min

Why epsilon moves exist at all

The definition

Where determinisation uses it

Epsilon moves add no power

Cost

Checking your own implementation

▾common follow-ups3 questions

▾red flags6 flags

Why epsilon moves exist at all

The definition

Where determinisation uses it

Epsilon moves add no power

Cost

Checking your own implementation

answer

go deeper