In the parity example, one DFA state summarizes the prefix already read. A nondeterministic automaton can have several possible current states after that same prefix. The useful deterministic summary is therefore a set of possibilities, rather than a guess about which path will succeed. This change in what a state remembers leads directly to subset construction.
We will distinguish three things throughout: a path through the NFA, the set of all possible endpoints, and the single DFA state representing that set. Keeping them separate prevents two common mistakes: rejecting because one branch fails, and accepting a whole word merely because an earlier prefix was accepted.
Define acceptance before simulating a machine
Definition 6.2.1
(NFA with empty transitions)
An -NFA is a tuple with a finite state set , finite input alphabet , start state , accepting states , and a transition function
Here is the set of all subsets of . A transition may have no destination, one destination, or several. An -transition changes state without consuming an input symbol; is not a symbol of the input alphabet. An ordinary NFA without -transitions is the special case in which every -successor set is empty.
A finite run is a path whose edge labels, after deleting the labels, spell the input word. The machine accepts a word if at least one such run starts at , consumes the whole word and ends in . Other runs may fail or end outside . No probability or random choice is part of this definition.
In transition tables below, an omitted edge is represented by the empty successor set . This differs from omitting a DFA transition: an NFA branch with no successor for the symbol being read dies, while other branches can continue.
Counterexample mode
One failed branch does not reject the word
Let loop on both 0 and 1, also allow , and let , where only accepts. There are no other edges.
On input 01, the run ends outside the accepting set. But consumes the same word and accepts. Selecting only the first run would give a false rejection. The correct simulation keeps both endpoints after reading 0, then all successors after reading 1.
This NFA recognizes words ending in 01: an accepting run must enter on the penultimate 0 and enter on the final 1, because has no outgoing edges. Conversely, any prefix can be read on 's loops before taking those final two edges.
Close under transitions that consume no input
Definition 6.2.2
(-closure)
For a subset , the -closure is the set of every state reachable from a member of using zero or more -edges. The zero-edge case matters: every seed state belongs to its own closure.
The closure operator satisfies
The first statement includes the seeds. For the second, concatenating two -paths still gives an -path, so closing an already closed set adds nothing. The third says that no state can be reached without any starting state. Do not confuse , a word with no symbols, with , a set with no states.
Worked example 6.2.3
(An -cycle has finitely many reachable endpoints)
Suppose and , with accepting and a 0-loop on . Then . The cycle gives arbitrarily long -walks but no further distinct states.
A worklist starts with the seeds, follows outgoing -edges, and adds a destination only if it has not been seen. Each state is added at most once, so a finite NFA cannot make this search loop forever. Taking the closure never consumes 0 or 1.
This example accepts the empty word, because its start closure contains . Reading another 0 returns to the same closed set, while reading 1 gives the empty set. Its language is therefore , including the empty word. Infinite -walks are not required for acceptance; the finite -edge from to already witnesses acceptance of the empty word.
Consume one symbol, then close the result
For an input symbol , collect all one-edge destinations by
If is already -closed, meaning , the next complete set of possibilities is
The existing closure accounts for -steps before consuming ; the new closure accounts for -steps afterwards. Raw move targets alone may therefore miss an accepting possibility.
Worked example 6.2.4
(A machine accepting exactly 0 and 01)
Take start state , accepting set , and the following complete successor table:
| State | Read 0 | Read 1 | -successors |
|---|---|---|---|
Reading 0 first produces the raw set . Its closure is , because the -edge is optional and consumes nothing. Thus 0 is accepted even though the raw move target is not accepting. From that closed set, reading 1 produces , so 01 is also accepted. No transition can consume another symbol from .
Now trace the longer input 010:
| Processed prefix | Raw targets of its last symbol | Committed -closed set | Would this prefix be accepted if input ended here? |
|---|---|---|---|
| No symbol yet | No | ||
0 | Yes | ||
01 | Yes | ||
010 | No |
The whole input 010 is rejected. Acceptance of either earlier prefix does not permit us to ignore the remaining input. An accepting state is not an instruction to stop the computation early.
Use the figure to trace the three machines above. On a move step the raw targets are only a preview; take -closure before committing the new subset. Compare a prefix verdict with the whole-word verdict.
Prove that the subset is an exact summary
Theorem 6.2.5
(Subsets track all runs exactly)
Let be an -NFA. For a word over , let be the set of states at which some run of from that consumes exactly can end; -steps are allowed before, between and after the symbols. Then for every word and symbol ,
and accepts if and only if .
Proof
(Induction on the number of consumed symbols)
For the empty word, a run can use only -edges, giving exactly the initial closure. Assume is correct. Any run consuming has a last symbol-consuming edge labeled . Before that edge, it has consumed and is at some state in ; after the edge, it may follow -edges. Its final state is therefore included by the move and closure.
Conversely, every state produced by the formula has a witness: a run for reaching a state in , then an -edge, then a finite -path. These pieces form a valid run for . Induction on word length proves both inclusions, so the subset is exact rather than an overestimate.
Finally, accepts exactly when some run for ends in , that is, when . The existential acceptance condition has become a simple set-intersection test, without choosing a single run.
Proof X-ray
Why the induction needs the closure twice
The induction is on the number of symbols in , not on the length of a run. An -cycle makes runs for one fixed word arbitrarily long, so run length gives no bound. Cutting each run at its last symbol-consuming edge does give one, because the part before the cut consumes the strictly shorter word .
Three facts do the work. First, is -closed by its definition: any run for can be extended by more -edges. The closure in the formula therefore supplies only the -steps that follow the new symbol; those before it already lie inside . Second, the inclusion decomposes a run and shows that no endpoint is missing, while glues three pieces into a run and shows that none is invented. Third, acceptance quantifies over runs, so only the set of endpoints matters: two runs that end in one state have the same possible futures.
Each closure is necessary. Starting from instead of breaks the base case: in the -cycle example misses the accepting , so the empty word would be rejected. Omitting the closure after the move breaks the step: in the machine accepting exactly 0 and 01, the raw target would reject 0. Finiteness of is not used in the equalities; it only makes each closure computable and the number of subsets finite.
Turn the reachable subsets into DFA states
Use each reachable -closed subset as one DFA state. The start state is , the transition on is , and a subset is accepting if it intersects . Each subset has exactly one successor subset for each symbol, which gives determinism even when it contains several NFA states.
Common mistake
(An accepting subset only needs to meet F)
A subset is not required to lie inside . In the machine accepting exactly 0 and 01, the subset reached after reading 0 contains the non-accepting , yet it must accept: the run ending in is a witness, and one witness suffices. Demanding would reject 0; the correct test is .
Build the transition table with a worklist: start with the initial subset; process each discovered subset once; compute its successor for every alphabet symbol; add a successor only if it is new. There are at most subsets, so the construction terminates. Equality here is set equality: and name the same DFA state.
Corollary 6.2.6
(Subset construction preserves the language)
Let be the DFA whose start state is , whose transition on is , and whose accepting states are the subsets meeting , restricted to the subsets reachable from the start. Then has at most states and .
Proof
(The DFA state after w is S_w)
The two equations of the previous theorem are exactly the start state and the transition rule of , so induction on shows that is in the state after reading . Every state of is a subset of , which gives the bound . Finally accepts if and only if , which is the condition for to accept .
Concept lensAlgebraic
The subset step as a Boolean matrix product
Write a set as a 0–1 row vector, the -edges as a Boolean matrix and the -edges as , with OR for addition and AND for multiplication. Since a state reachable by -edges is reachable by fewer than of them, is multiplication by , and is . For the machine accepting exactly and , is , its product with is , and the closure gives , the set .
Worked example 6.2.7
(Subset construction for the machines above)
For the machine accepting 0 or 01, name the reachable subsets
| DFA state | On 0 | On 1 | Accepting? |
|---|---|---|---|
| (start) | No | ||
| Yes | |||
| Yes | |||
| No |
The empty subset is an ordinary rejecting DFA state: no run remains, and neither symbol can create one from nothing. Include it when it is reachable, as it is here. By contrast, the earlier NFA for words ending in 01 always retains the possibility , so its reachable subsets are only , and ; the empty subset is unreachable.
Name these three subsets , and . Each row is computed from , , , with no other edges:
| DFA state | On 0 | On 1 | Accepting? |
|---|---|---|---|
| (start) | No | ||
| No | |||
| Yes |
The word 0101 visits and is accepted; 010 ends in and is rejected; the empty word stays in the rejecting start state .
Common mistake
(The DFA has no column)
The DFA table has one column for each symbol of and none for . The -edges of the NFA have been absorbed into the closures that define each subset, and a deterministic machine has no move that consumes no input. A table with an column describes a different kind of machine.
Subset construction preserves the language but is not a minimization algorithm. Its exponential upper bound is a bound on possible subsets, not a claim that every NFA reaches every subset.
Counterexample mode
Two accepting subsets can require different future behavior
In the four-state table, both and accept the current prefix. They still cannot be merged merely on that basis: the suffix 1 takes to accepting , but takes to rejecting . Appending 1 to accepted prefix 0 gives accepted 01; appending the same suffix to accepted prefix 01 gives rejected 011.
State equivalence requires agreement on every continuation, not just agreement about whether to accept now. This is the same kind of distinction used when proving that the parity DFA needs its different parity states.
Implement the invariant directly
The following Python program uses sets of state names. Missing dictionary entries mean empty successor sets, and inputs are words over . The empty word is the empty Python string "", not the literal character "ε".
def epsilon_closure(seeds, epsilon):
seen = set(seeds)
pending = list(seen)
while pending:
state = pending.pop()
for target in epsilon.get(state, ()):
if target not in seen:
seen.add(target)
pending.append(target)
return frozenset(seen)
def step(states, symbol, transitions, epsilon):
targets = {
target
for state in states
for target in transitions.get((state, symbol), ())
}
return epsilon_closure(targets, epsilon)
def accepts(word, start, accepting, transitions, epsilon):
states = epsilon_closure({start}, epsilon)
for symbol in word:
states = step(states, symbol, transitions, epsilon)
return not states.isdisjoint(accepting)
transitions = {("q0", "0"): {"q1"}, ("q1", "1"): {"q2"}}
epsilon = {"q1": {"q2"}}
for word in ["0", "01", "010", ""]:
print(repr(word), accepts(word, "q0", {"q2"}, transitions, epsilon))
The Boolean outputs are True, True, False, False. The worklist's visited set prevents -cycles from being explored endlessly. frozenset gives an immutable representation suitable for naming DFA subsets later. No branch history is stored: when two runs meet at one state after the same prefix, their possible continuations depend on that state, so one set membership suffices.
The code deliberately updates states only after both the move and its closure are complete. During a hand trace, label raw targets separately from the committed state for the consumed prefix; otherwise a table can claim to have consumed a symbol while still displaying a set for the previous prefix.
Exercises
Quick check
(Compute closure before checking the empty word)
In the -cycle example, compute and . Is the empty word accepted? Why does a visited set terminate even though the cycle permits infinitely many walks?
Solution · Answer
The closures are and . The empty word is accepted because the initial closure contains accepting . The search records distinct states rather than complete walks; each of the two states is added once, after which revisiting it adds no worklist entry.
Quick check
(Keep all branches for a suffix language)
For the NFA accepting words ending in 01, trace the subsets for 010. Which prefixes would be accepted, and why is the whole word rejected?
Solution · Answer
The subsets are initially, then , and . Only prefix 01 has an accepting endpoint. The final subset for 010 contains no , so the whole word is rejected. The branch staying at survives, but that state is not accepting.
Quick check
(Explain why raw targets can give a false rejection)
In the NFA accepting exactly 0 or 01, a simulation reads 0, obtains raw targets and rejects because . Identify the missing operation and give the correct final acceptance test.
Solution · Answer
Take -closure after the symbol move. It adds while retaining , giving . Its intersection with is nonempty, so 0 is accepted. The -edge consumes no extra input symbol and must be considered even when no symbols remain.
Quick check
(Separate reachability from the power-set bound)
The three-state suffix NFA has at most eight possible subsets. Why does its constructed DFA have only three reachable states, and why should a separate empty trap not be counted as reachable? What different question would minimization ask?
Solution · Answer
The start subset contains , and has a loop on each symbol, so every reached subset retains it. The transition rules generate exactly , and ; all three are reached by , 0 and 01. None is empty. The upper bound counts all subsets, including unreachable ones. Minimization instead asks whether any reachable DFA states agree on every continuation and can therefore be identified without changing the language.