skip to content

How does the subset construction turn a nondeterministic finite automaton into a deterministic one, and what is a single resulting state?

level: middleimportance: should knowfreq 48%

answer

  1. name the live set
  2. a state of the result is a set
  3. union the successors, then close
  4. any accepting member makes it accepting
  5. empty subset is the self-looping trap

basics

~20 s

Each state of the deterministic machine is a whole set of nondeterministic states — exactly those a prefix could have reached. Transitions map a set to the union of its members' successors, the empty set is the trap, and a set accepts if any member does.

solid answer

~40 s

The construction names the **live set** and makes it a state. Start from the epsilon-closure of `{start}`. For each subset already discovered and each alphabet symbol `a`, compute the union of `move(q, a)` over every `q` in the subset, close it under epsilon moves, and record that as the subset's row for `a`. Any subset you have not seen before goes on a worklist and gets its own row later; you stop when the worklist drains. A subset is **accepting** when it contains at least one accepting state of the original, and the **empty subset** is a legitimate non-accepting trap that maps to itself on every symbol. The result is total and deterministic, with at most `2^n` states for `n` original states — often far fewer, because only reachable subsets are built.

code

pseudocode · 17 lines
pseudocode
start <- epsilon_closure({q0})
states <- { start }
work  <- [ start ]

while work is not empty:
    S <- pop(work)
    for each symbol a in alphabet:
        T <- empty set
        for each state q in S:
            T <- T union move(q, a)
        T <- epsilon_closure(T)      // empty set closes to empty set
        transition[S][a] <- T        // T may be empty: that is the trap
        if T not in states:
            add T to states
            push T onto work

accepting <- { S in states : S contains some accepting state }

go deeper

for a junior

Recall the headline: each state of the new machine is a set of old states, and the new machine follows all branches at once instead of choosing one.

for a middle

Walk the algorithm aloud — start closure, union of successors, close again, worklist for unseen subsets — and state the acceptance rule and the empty-subset trap correctly.

for a senior

Be explicit that the construction trades match-time work for build time and table memory, and that only reachable subsets are built, so the exponential bound is worst case, not typical.

for a principal

Treat the table as a capacity question: bound the subset count for the machines you actually generate, and decide what happens when a generated machine exceeds the ceiling.

## The idea in one line Simulating a nondeterministic acceptor means carrying the **set of states it could be in**. That set is finite, it is determined entirely by the prefix read so far, and it updates deterministically. So give each such set a name and you have a deterministic machine. That is the whole of the **subset construction** (also called the powerset construction). ## The recipe Given a nondeterministic machine with state set `Q`, alphabet `A`, start state `q0` and accepting set `F`: 1. **Start subset** — `S0 = closure({q0})`. Put it on a worklist. 2. **Step** — pop a subset `S`. For each symbol `a` in `A`, compute `T = closure( union of move(q, a) for every q in S )` and record `transition[S][a] = T`. 3. **Discover** — if `T` has not been seen before, add it to the machine and push it on the worklist. 4. **Repeat** until the worklist is empty. 5. **Accepting** — a subset is accepting exactly when it contains **at least one** member of `F`. The result is **total**: every subset has a row for every symbol, because the union may legitimately come out empty and the empty set is itself a subset. ## The parts people get wrong - **A state of the result is a set, not a choice.** It is not "the most likely branch" and not a path; it is *the exact collection of original states a prefix could have reached*. - **Acceptance is existential, again.** A subset accepts if **any** member is accepting — not if all are, and not if the start state is present. - **The empty subset is a real state.** It means every branch has died. Because `move` over an empty set is empty and the closure of the empty set is empty, it maps to itself on every symbol: a non-accepting **trap**. Dropping it leaves the transition function partial, which is the usual way a hand-written converter ends up with a machine that is not deterministic at all. - **Only reachable subsets are built.** The `2^n` figure is an **upper bound**, not a prediction. Many machines determinise to something small; the worklist never enumerates the powerset, it explores it. ## A worked shape Take a sensor whose nondeterministic machine idles on the start state `s` for every byte and, on seeing a marker, also guesses that a signature starts here, moving to `m`; from `m`, any byte leads to the accepting state `f`. So `Q = {s, m, f}` and the language is "the second-to-last byte is a marker". | Subset | on marker | on any other byte | accepting? | |---|---|---|---| | `{s}` | `{s, m}` | `{s}` | no | | `{s, m}` | `{s, m, f}` | `{s, f}` | no | | `{s, m, f}` | `{s, m, f}` | `{s, f}` | **yes** | | `{s, f}` | `{s, m}` | `{s}` | **yes** | Four reachable subsets out of the eight the bound allows, and the empty subset never appears because `s` idles on every byte and is therefore in every reachable subset. That is typical: the bound is loose until the machine is built to be awkward. ## Cost, and where it is paid | Property | Nondeterministic original | Determinised result | |---|---|---| | States | `n` | up to `2^n` reachable subsets | | Per-symbol work | proportional to the live set and its edges | one table lookup | | Build cost | none | one closure and one union per subset per symbol | | Memory | `n` bits of live set | the table: states times alphabet | The construction moves cost from **match time** to **build time and memory**. That is the trade it exists to make. Whether it is worth making — up front, on demand, or not at all — is a separate design decision. ## Boundaries The subset construction says nothing about whether the machine it produces is as small as possible; duplicate-behaviour subsets are common and collapsing them is a different procedure entirely. Nor does it say how the nondeterministic machine was obtained in the first place — building one from pattern operators is its own construction.

  • Why is the empty subset kept as a state rather than discarded?
    It represents "every branch has died", and keeping it makes the transition function total — every subset has a successor on every symbol. Because the union over an empty set is empty and its closure is empty, it maps to itself on every symbol, giving a non-accepting trap. Discarding it leaves a partial, non-deterministic table.
  • Does the worklist ever enumerate all 2^n subsets?
    Only when all of them are reachable. The worklist explores subsets forward from the start subset, so it builds exactly the reachable ones. For many machines that is a handful; `2^n` is an upper bound that a deliberately awkward machine can approach, not a typical outcome.
  • Is the machine the construction produces the smallest deterministic one for that language?
    Not in general. Two distinct subsets can behave identically on every future input, and the construction has no mechanism for noticing that — it stops as soon as the worklist drains. Collapsing behaviourally identical states, and proving a state count cannot be beaten, is a separate procedure.

saying these in an interview costs you the question

  • Says a subset state is one chosen branch of the original machine
  • Marks a subset accepting only when all its members are accepting
  • Drops the empty subset, leaving the transition table partial
  • Claims the construction always produces exactly 2^n states
  • Forgets the epsilon-closure after the union of successors
  • Assumes the resulting deterministic machine is automatically minimal