NFA to DFA conversion — subset construction: Worked examples

Before starting, make sure these are solid: Finite Automata — NFA and ε-NFA (what an NFA and an ε-move are), Finite Automata — DFA basics (what a single-state machine is), and Power Set and Subsets (why there are $2^{n}$ subsets of an $n$ -element set).

The scenario matrix

Every subset-construction problem is really one of these case classes. If we work an example of each, you will never meet a cell you haven't seen.

#	Case class	What's tricky about it	Covered by
C1	No ε-edges (plain NFA)	ECLOSE does nothing — pure MOVE	Example 1
C2	With ε-edges (chained / ε-cycle)	must close before start and after every move; closures can iterate	Example 2
C3	Dead / trap state appears ( $\emptyset$ )	a MOVE returns the empty set	Example 3
C4	Start state is itself accepting	the empty string $ε$ must be accepted	Example 4
C5	Blow-up: near $2^{n}$ reachable subsets	many subsets actually reachable	Example 5
C6	Degenerate: no final state at all	language is empty — every subset rejects	Example 6
C7	Word problem (real-world spec)	translate English → NFA → DFA	Example 7
C8	Exam twist: unreachable subsets	don't list all $2^{n}$ ; only reachable ones	Example 8

Notation reminder, so nothing is used before it's earned:

A subset-state is written ${q_{0}, q_{2}}$ — literally the set of NFA states the NFA might be sitting in. This is one DFA state.
$MOVE (S, a)$ = union of all $a$ -arrows leaving the states in $S$ .
$ECLOSE (S)$ = $S$ plus everything reachable by following $ε$ -arrows only.
$S \cap F \neq = \emptyset$ means " $S$ shares at least one state with the final set $F$ " — that " $\cap$ " is set intersection, and " $\neq = \emptyset$ " means "the overlap is not empty".

Throughout, the pictures carry the work: magenta circles are non-accepting DFA states, violet double circles are accepting, orange is the dead/trap state, and the orange start arrow marks the start. Watch the arrows, not just the tables.

Example 1 — Case C1 (no ε)

Step 1 — start state. $q_{0}^{'} = ECLOSE ({p}) = {p}$ . Call it $A$ . Why this step? Because there are no ε-edges, ECLOSE cannot add anything — for case C1 the start is just ${p}$ .

Step 2 — $A$ on $0$ . $MOVE ({p}, 0) = {p} = A$ . Why? Only state in the set is $p$ ; its $0$ -arrow returns ${p}$ . No ε ⇒ ECLOSE unchanged. Self-loop.

Step 3 — $A$ on $1$ . $MOVE ({p}, 1) = {p, q}$ . New subset — call it $B = {p, q}$ . Why? $p$ 's $1$ -arrow is ${p, q}$ . This subset hasn't appeared, so it's a brand-new DFA state.

Step 4 — $B$ on $0$ . $MOVE ({p, q}, 0) = {p} \cup {q} = {p, q} = B$ . Self-loop.

Step 5 — $B$ on $1$ . $MOVE ({p, q}, 1) = {p, q} \cup \emptyset = {p, q} = B$ . Self-loop.

Step 6 — accepting? $A \cap {q} = \emptyset$ → no. $B \cap {q} = {q}$ → yes.

The finished DFA — look at how the orange start arrow enters $A$ , and how every arrow out of $B$ curls back to $B$ (once you have seen a $1$ you can never lose it):

Figure — NFA to DFA conversion — subset construction

DFA state	on 0	on 1	accept?
$A = {p}$ (start)	$A$	$B$	no
$B = {p, q}$	$B$	$B$	yes

Verify: we reach $B$ exactly once we've read a $1$ , and once in $B$ we stay there. So the DFA accepts every string containing at least one $1$ . Trace " $00$ ": $A \to A \to A$ , reject (correct — no 1). Trace " $01$ ": $A \to A \to B$ , accept. ✔ Only 2 of $2^{2} = 4$ subsets reachable.

Example 2 — Case C2 (ε-edges, with a chained ε-closure and an ε-cycle)

Step 1 — start (chained closure, needs several iterations). $ECLOSE ({0})$ :

Iteration 1: from $0$ , ε-edge to $1$ → set now ${0, 1}$ .
Iteration 2: from the newly added $1$ , ε-edge to $2$ → set now ${0, 1, 2}$ .
Iteration 3: from the newly added $2$ , no ε-edge → nothing new, stop.

Start $= {0, 1, 2} = A$ . Why iterate? ECLOSE is a fixed-point computation: after adding $1$ you must re-scan $1$ 's ε-edges, which reveal $2$ . A single pass that only looked at $0$ would wrongly stop at ${0, 1}$ . This is the chained-ε pitfall the parent note only hinted at.

Step 2 — $A$ on $a$ . $MOVE ({0, 1, 2}, a) = {3}$ (only $2$ has an $a$ -arrow). Then $ECLOSE ({3})$ : from $3$ , ε-edge to $2$ → ${2, 3}$ ; from $2$ , no ε → stop. New state $B = {2, 3}$ . Why does the ε-cycle not loop forever? The set ${2, 3}$ already contains both $2$ and $3$ ; ECLOSE only adds states, so once nothing new can be added it halts — even though $2 ⇄ 3$ visually cycles.

Step 3 — $A$ on $b$ . $MOVE ({0, 1, 2}, b) = \emptyset$ . ECLOSE $(\emptyset) = \emptyset$ . Dead state — call it $\emptyset$ . (Foreshadows C3.) Why is MOVE empty here? We scan every state in $A = {0, 1, 2}$ for a $b$ -arrow: state $0$ has none, state $1$ has none, state $2$ has none. The union of three empty sets is empty — so there is literally nowhere to go on $b$ .

Step 4 — $B$ on $a$ . $MOVE ({2, 3}, a)$ : $2$ 's $a$ -arrow is ${3}$ , $3$ has no $a$ -arrow → ${3}$ . ECLOSE $({3}) = {2, 3} = B$ . Self-loop.

Step 5 — $B$ on $b$ . $MOVE ({2, 3}, b)$ : $2$ has no $b$ -arrow, $3$ 's $b$ -arrow is ${3}$ → ${3}$ . ECLOSE $({3}) = {2, 3} = B$ . Self-loop.

Step 6 — accepting? $B = {2, 3}$ contains $3$ → yes. $A = {0, 1, 2}$ has no $3$ → no. $\emptyset$ → no.

The DFA — note the orange dead state hanging off $A$ on $b$ , and $B$ looping to itself on both letters:

DFA state	on $a$	on $b$	accept?
$A = {0, 1, 2}$ (start)	$B$	$\emptyset$	no
$B = {2, 3}$	$B$	$B$	yes
$\emptyset$ (dead)	$\emptyset$	$\emptyset$	no

Verify: to accept, we must first read an $a$ (moving $A \to B$ ); after that any mix of $a$ 's and $b$ 's keeps us in $B$ . So the language is " $a$ followed by any string over ${a, b}$ " = $a (a + b)^{*}$ . Trace " $a$ ": $A \to B$ (accept). Trace " $ab$ ": $A \to B \to B$ (accept). Trace " $b$ ": $A \to \emptyset$ (reject). Trace " $ba$ ": $A \to \emptyset \to \emptyset$ (reject). ✔ And the start subset really needed three closure iterations to build.

Example 3 — Case C3 (dead/trap state)

Step 1 — start. $ECLOSE ({s}) = {s} = A$ (no ε).

Step 2 — $A$ on $a$ . $MOVE ({s}, a) = {t} = B$ .

Step 3 — $B$ on $a$ . $MOVE ({t}, a) = \emptyset$ . This is the empty subset — the DFA's dead state $\emptyset$ . Why this step matters? The NFA has no live states after $aa$ , so it can never reach a final state again. In a DFA every transition must be defined, so we make $\emptyset$ a real state that loops to itself forever (Mistake 5 from parent).

Step 4 — $\emptyset$ on $a$ $= \emptyset = \emptyset$ . Self-loop, never accepts.

The trap is easiest to see — once the orange dead state is entered, every arrow curls back into it:

DFA state	on $a$	accept?
$A = {s}$ (start)	$B$	no
$B = {t}$	$\emptyset$	yes
$\emptyset$ (dead)	$\emptyset$	no

Verify: language is exactly the single string " $a$ ". Trace " $a$ ": $A \to B$ , accept. Trace " $aa$ ": $A \to B \to \emptyset$ , reject forever. Trace "" : stays $A$ , reject. ✔ This DFA recognises ${a}$ — one string only.

Example 4 — Case C4 (start is accepting, accepts $ε$ )

Step 1 — start. $ECLOSE ({u}) = {u} = A$ .

Step 2 — is the START accepting? $A \cap F = {u} \cap {u} = {u} \neq = \emptyset$ → yes, $A$ is accepting. Why this step is easy to miss? People check accepting states after building transitions and forget the start can already be final — that is exactly how you accept the empty string $ε$ (the DFA halts on $A$ having read nothing).

Step 3 — $A$ on $a$ . $MOVE ({u}, a) = {v} = B$ .

Step 4 — $B$ on $a$ . $MOVE ({v}, a) = {u} = A$ .

DFA state	on $a$	accept?
$A = {u}$ (start)	$B$	yes
$B = {v}$	$A$	no

Verify: language is "even number of $a$ 's" (including zero) = $(aa)^{*}$ . Trace "" : at $A$ , accept. Trace " $a$ ": $A \to B$ , reject. Trace " $aa$ ": $A \to B \to A$ , accept. ✔

Example 5 — Case C5 (near $2^{n}$ blow-up)

Step 1 — start. $ECLOSE ({r_{0}}) = {r_{0}} = A$ (no ε).

Step 2 — $A$ on $0$ : $MOVE ({r_{0}}, 0) = {r_{0}} = A$ . $A$ on $1$ : ${r_{0}, r_{1}} = B$ . Why $B$ is new? The $1$ -arrow of $r_{0}$ is nondeterministic ( ${r_{0}, r_{1}}$ ), giving a genuinely bigger subset.

Step 3 — $B$ on $0$ : $MOVE ({r_{0}, r_{1}}, 0) = {r_{0}} \cup {r_{2}} = {r_{0}, r_{2}} = C$ . $B$ on $1$ : ${r_{0}, r_{1}} \cup {r_{2}} = {r_{0}, r_{1}, r_{2}} = D$ .

Step 4 — $C = {r_{0}, r_{2}}$ on $0$ : ${r_{0}} \cup \emptyset = {r_{0}} = A$ . on $1$ : ${r_{0}, r_{1}} \cup \emptyset = {r_{0}, r_{1}} = B$ . Why does $r_{2}$ contribute nothing? $r_{2}$ has no outgoing arrows — it's a sink in the NFA.

Step 5 — $D = {r_{0}, r_{1}, r_{2}}$ on $0$ : ${r_{0}} \cup {r_{2}} \cup \emptyset = {r_{0}, r_{2}} = C$ . on $1$ : ${r_{0}, r_{1}} \cup {r_{2}} \cup \emptyset = {r_{0}, r_{1}, r_{2}} = D$ .

DFA state	on $0$	on $1$	accept?
$A = {r_{0}}$ (start)	$A$	$B$	no
$B = {r_{0}, r_{1}}$	$C$	$D$	no
$C = {r_{0}, r_{2}}$	$A$	$B$	yes
$D = {r_{0}, r_{1}, r_{2}}$	$C$	$D$	yes

Verify: $C, D$ both contain $r_{2}$ → accepting. Language: strings whose 2nd-last symbol is $1$ . Trace " $10$ ": $A \to B \to C$ (accept — 2nd-last is $1$ ). Trace " $01$ ": $A \to A \to B$ (reject — 2nd-last is $0$ ). Trace " $110$ ": $A \to B \to D \to C$ (accept). ✔ 4 of 8 subsets reachable — for the general " $n$ -th from end" NFA, all $2^{n}$ become reachable, the true exponential blow-up.

Example 6 — Case C6 (no final state → empty language)

Step 1 — start. $ECLOSE ({x}) = {x} = A$ .

Step 2 — transitions: $A$ on $a \to {y} = B$ ; $B$ on $a \to {x} = A$ .

Step 3 — accepting? For any subset $S$ , $S \cap F = S \cap \emptyset = \emptyset$ . Why this settles it? Intersecting with the empty set is always empty, so no subset can be accepting — no matter how the transitions look.

DFA state	on $a$	accept?
$A = {x}$ (start)	$B$	no
$B = {y}$	$A$	no

Verify: language $= \emptyset$ (the empty language — not the same as ${ε}$ !). Every string is rejected because no DFA state is accepting. ✔ This is the mechanical reason "no final states ⇒ empty language" — the subset construction reproduces it automatically.

Example 7 — Case C7 (word problem)

Step 0 — build the NFA (why an NFA first?). NFAs let us "guess" when the crucial $p$ occurs, which is far easier than tracking it deterministically. States ${w_{0}, w_{1}, w_{2}}$ , start $w_{0}$ , final ${w_{2}}$ : $δ (w_{0}, p) = {w_{0}, w_{1}}$ , $δ (w_{0}, q) = {w_{0}}$ , $δ (w_{1}, q) = {w_{2}}$ , $δ (w_{2}, p) = {w_{2}}$ , $δ (w_{2}, q) = {w_{2}}$ . (In $w_{0}$ , reading $p$ either ignores it or "commits" to it via $w_{1}$ ; from $w_{1}$ a later $q$ unlocks to $w_{2}$ , which then loops forever.)

Step 1 — start. $ECLOSE ({w_{0}}) = {w_{0}} = A$ .

Step 2 — $A$ on $p$ : ${w_{0}, w_{1}} = B$ . $A$ on $q$ : ${w_{0}} = A$ . Why? Before any $p$ , a $q$ is useless — stay at $A$ .

Step 3 — $B = {w_{0}, w_{1}}$ on $p$ : ${w_{0}, w_{1}} \cup \emptyset = {w_{0}, w_{1}} = B$ . on $q$ : ${w_{0}} \cup {w_{2}} = {w_{0}, w_{2}} = C$ .

Step 4 — $C = {w_{0}, w_{2}}$ on $p$ : ${w_{0}, w_{1}} \cup {w_{2}} = {w_{0}, w_{1}, w_{2}} = D$ . on $q$ : ${w_{0}} \cup {w_{2}} = {w_{0}, w_{2}} = C$ .

Step 5 — $D = {w_{0}, w_{1}, w_{2}}$ on $p$ : ${w_{0}, w_{1}} \cup {w_{2}} = {w_{0}, w_{1}, w_{2}} = D$ . on $q$ : ${w_{0}} \cup {w_{2}} \cup {w_{2}} = {w_{0}, w_{2}} = C$ .

Step 6 — accepting? Contains $w_{2}$ : $C$ and $D$ → yes. $A, B$ → no.

DFA state	on $p$	on $q$	accept?
$A = {w_{0}}$ (start)	$B$	$A$	no
$B = {w_{0}, w_{1}}$	$B$	$C$	no
$C = {w_{0}, w_{2}}$	$D$	$C$	yes
$D = {w_{0}, w_{1}, w_{2}}$	$D$	$C$	yes

Verify: once we hit $C$ or $D$ (unlocked), every arrow keeps us among ${C, D}$ — so it stays unlocked, matching the forecast. Trace " $pq$ ": $A \to B \to C$ (unlock). Trace " $q p$ ": $A \to A \to B$ (still locked — the $q$ came before $p$ ). Trace " $pq p$ ": $A \to B \to C \to D$ (unlocked). ✔

Example 8 — Case C8 (exam twist: don't enumerate all $2^{n}$ )

Step 1 — start. $ECLOSE ({m_{0}}) = {m_{0}} = A$ (no ε).

Step 2 — reachability only. $A = {m_{0}}$ on $a$ : $MOVE ({m_{0}}, a) = {m_{1}} = B$ ; on $b$ : $MOVE ({m_{0}}, b) = \emptyset = \emptyset$ . Why only reachable? Mistake 3 from the parent note: unreachable subsets are dead weight. We generate a subset only when an arrow lands on it.

Step 3 — process $B = {m_{1}}$ . on $a$ : $MOVE ({m_{1}}, a) = \emptyset = \emptyset$ ; on $b$ : $MOVE ({m_{1}}, b) = {m_{2}} = C$ .

Step 4 — process $C = {m_{2}}$ . on $a$ : $MOVE ({m_{2}}, a) = {m_{2}} = C$ ; on $b$ : $MOVE ({m_{2}}, b) = {m_{2}} = C$ . Both self-loops.

Step 5 — process $\emptyset$ . on $a, b \to \emptyset = \emptyset$ . Dead state.

Step 6 — accepting? $C = {m_{2}}$ contains $m_{2}$ → yes. $A, B, \emptyset$ → no.

DFA state	on $a$	on $b$	accept?
$A = {m_{0}}$ (start)	$B$	$\emptyset$	no
$B = {m_{1}}$	$\emptyset$	$C$	no
$C = {m_{2}}$	$C$	$C$	yes
$\emptyset$ (dead)	$\emptyset$	$\emptyset$	no

Verify: reachable subsets $= {A, B, C, \emptyset}$ = 4 of 8. The 4 unreachable subsets ( ${m_{0}, m_{1}}$ , ${m_{0}, m_{2}}$ , ${m_{1}, m_{2}}$ , ${m_{0}, m_{1}, m_{2}}$ ) never occur because this NFA's arrows are single-valued (no nondeterministic branching), so no subset ever grows past size 1. Language: $ab (a + b)^{*}$ = "starts with $ab$ ". Trace " $ab$ ": $A \to B \to C$ (accept). Trace " $ba$ ": $A \to \emptyset \to \emptyset$ (reject). Trace " $aba$ ": $A \to B \to C \to C$ (accept). ✔

Recall Self-test: name the case class

Which cell does an NFA with no final states hit, and what's the resulting language? ::: Case C6 — the empty language $\emptyset$ ; every subset rejects because $S \cap \emptyset = \emptyset$ . Which cell forces you to accept the empty string $ε$ ? ::: Case C4 — the start subset already contains a final state. When does the dead state $\emptyset$ get created? ::: Case C3 — whenever a MOVE returns the empty set; it self-loops and rejects. Why did Example 2's start subset need three closure iterations? ::: The ε-edges chain $0 \to 1 \to 2$ ; you must re-scan each newly added state, so a single pass would wrongly stop at ${0, 1}$ . Why did Example 5 reach 4 subsets while Example 8's subsets never grew past size 1? ::: Example 5's NFA branches nondeterministically (subsets grow); Example 8's arrows are single-valued, so subsets stay singletons plus the dead state.

Connections

Parent: subset construction
Finite Automata — DFA basics
Finite Automata — NFA and ε-NFA
Power Set and Subsets
Regular Expressions to NFA — Thompson's construction
DFA Minimization — Myhill–Nerode
Closure Properties of Regular Languages
Pumping Lemma for Regular Languages