Notebook 3: From NFA to DFA — the Subset Construction

Interactive walkthrough of the subset construction algorithm that converts any NFA into an equivalent DFA. Works through the running example from the VVT course at the University of Udine.

Subset Construction (NFA → DFA)

This notebook walks through the subset construction algorithm that converts any NFA into an equivalent DFA. The running example is the NFA that accepts exactly the words over \(\{a,b\}\) that end in the letter \(a\).

NFA states:

  • \(q_s\) — scanning (initial, non-accepting)
  • \(q_a\) — accept (accepting)

NFA transitions: \(\Delta(q_s,a)=\{q_s,q_a\}\), \(\Delta(q_s,b)=\{q_s\}\), \(\Delta(q_a,\cdot)=\varnothing\).

Widget 1: Step-by-Step Worklist Construction

Click Step → to advance the algorithm one micro-step at a time.

Step 0 / 20
WORKLIST
PROCESSED

NFA

a, b a qₛ qₐ

DFA Transition Table

State a b

Widget 2: Word Simulation

Type a word over \(\{a,b\}\) (default aba) and step through it. Each step reads one symbol and shows both the NFA active-state set and the current DFA state — demonstrating the invariant: DFA state = set of active NFA states.

NFA — active states

a, b a qₛ qₐ

DFA — current state

b a a b S₀ {qₛ} S₁ ★ {qₛ,qₐ}

Simulation trace

Prefix NFA active states DFA state Accepted?

What To Notice

  1. Only 2 reachable DFA states out of 4 possible. A 2-state NFA could produce up to \(2^2 = 4\) subset states (\(\varnothing\), \(\{q_s\}\), \(\{q_a\}\), \(\{q_s,q_a\}\)), but the worklist algorithm discovered only \(\{q_s\}\) and \(\{q_s,q_a\}\).

  2. \(\{q_a\}\) is unreachable. \(q_a\) is only reached from \(q_s\) via the \(a\)-arc. Since \(q_a\) has no outgoing transitions, it can never appear alone in an active set — it always arrives together with \(q_s\) (which keeps itself alive via the self-loop). Hence \(\{q_a\}\) is never generated by the worklist.

  3. The invariant in action. At every moment in Widget 2 the DFA-state label is the NFA active set. The subset construction packages the power-set computation into a single deterministic state name.

  4. Acceptance corresponds to \(S \cap F \neq \varnothing\). A DFA state \(S\) is accepting precisely when it contains at least one NFA accepting state (\(q_a \in S\)). That is why only \(\{q_s,q_a\}\) is a DFA accepting state, reflecting that the word prefix read so far ends in \(a\).