NFA to DFA conversion — subset construction: Exercises

Intuition How to use this page

Cover the solutions. Try each problem cold. Every symbol here was built in the parent NFA to DFA — subset construction note — if a symbol feels unfamiliar, re-read that note first. We climb five levels: L1 Recognition (do you know the pieces?) → L2 Application (run the machine) → L3 Analysis (why does it behave this way?) → L4 Synthesis (assemble a whole conversion) → L5 Mastery (push the limits).

Notation note: we write the NFA transition function as $δ_{N}$ everywhere, matching the parent note. When a single small NFA is on the table and no confusion is possible, we abbreviate $δ_{N}$ to $δ$ — the two mean exactly the same thing (the unqualified $δ$ is always the NFA's transition function on this page).

Reminders of the two engines you will use everywhere:

$ECLOSE (S)$ = every state you can reach from $S$ by ε-edges only, $S$ itself included.
$MOVE (S, a) = ⋃_{q \in S} δ_{N} (q, a)$ = every state reachable on reading $a$ .
DFA step: $δ_{D} (S, a) = ECLOSE (MOVE (S, a))$ .

Level 1 — Recognition

Exercise 1.1

An NFA has ε-edges $0 ε 1$ and $1 ε 3$ , and no other ε-edges. Compute $ECLOSE ({0})$ and $ECLOSE ({3})$ .

Recall Solution

What ECLOSE asks: "starting from these states, where can I silently drift using only ε-arrows?" — and you always include where you started.

From $0$ : an ε-edge takes you to $1$ ; from $1$ another ε-edge takes you to $3$ ; from $3$ nothing. So you collect $0, 1, 3$ . $ECLOSE ({0}) = {0, 1, 3} .$ From $3$ : no ε-edges leave it, so you collect only itself. $ECLOSE ({3}) = {3} .$ Why $3$ is included in its own closure: ECLOSE always contains its input set — "reachable in zero ε-steps" counts.

Exercise 1.2

NFA over $Σ = {a, b}$ with $δ_{N} (p, a) = {p, r}$ , $δ_{N} (q, a) = {r}$ , and no $a$ -edge from $r$ . Compute $MOVE ({p, q}, a)$ and $MOVE ({r}, a)$ .

Recall Solution

What MOVE asks: "reading exactly one $a$ , which states could each member of my set jump to?" — then pool all those together.

$MOVE ({p, q}, a) = δ_{N} (p, a) \cup δ_{N} (q, a) = {p, r} \cup {r} = {p, r} .$ $MOVE ({r}, a) = \emptyset$ , because $r$ has no $a$ -edge. An empty MOVE is legal — it signals the machine "dies" on that step.

Exercise 1.3

An NFA has $n = 4$ states. What is the maximum possible number of DFA states the subset construction can create, and what does the state $\emptyset$ represent?

Recall Solution

Each DFA state is a subset of the $4$ NFA states, and the number of subsets of a 4-element set is $2^{4} = 16$ (see Power Set and Subsets). $max DFA states = 2^{4} = 16.$ $\emptyset$ = the dead/trap state: no NFA states are alive, so nothing can ever accept again. It loops to itself on every symbol and rejects.

Level 2 — Application

Exercise 2.1

NFA over $Σ = {a, b}$ , states ${q_{0}, q_{1}, q_{2}}$ , start $q_{0}$ , final ${q_{2}}$ , no ε: $δ_{N} (q_{0}, a) = {q_{0}, q_{1}}$ , $δ_{N} (q_{0}, b) = {q_{0}}$ , $δ_{N} (q_{1}, b) = {q_{2}}$ , $δ_{N} (q_{2}, a) = {q_{2}}$ , $δ_{N} (q_{2}, b) = {q_{2}}$ . Build the DFA transition table (reachable states only) and list its accepting states.

Recall Solution

Start: no ε-edges, so $q_{0}^{'} = ECLOSE ({q_{0}}) = {q_{0}}$ . Call it $A$ .

$A = {q_{0}}$ :

on $a$ : $MOVE = {q_{0}, q_{1}}$ → new state $B = {q_{0}, q_{1}}$ .
on $b$ : $MOVE = {q_{0}} = A$ .

$B = {q_{0}, q_{1}}$ :

on $a$ : $δ_{N} (q_{0}, a) \cup δ_{N} (q_{1}, a) = {q_{0}, q_{1}} \cup \emptyset = {q_{0}, q_{1}} = B$ .
on $b$ : $δ_{N} (q_{0}, b) \cup δ_{N} (q_{1}, b) = {q_{0}} \cup {q_{2}} = {q_{0}, q_{2}}$ → new state $C$ .

$C = {q_{0}, q_{2}}$ :

on $a$ : ${q_{0}, q_{1}} \cup {q_{2}} = {q_{0}, q_{1}, q_{2}}$ → new state $D$ .
on $b$ : ${q_{0}} \cup {q_{2}} = {q_{0}, q_{2}} = C$ .

$D = {q_{0}, q_{1}, q_{2}}$ :

on $a$ : ${q_{0}, q_{1}} \cup \emptyset \cup {q_{2}} = {q_{0}, q_{1}, q_{2}} = D$ .
on $b$ : ${q_{0}} \cup {q_{2}} \cup {q_{2}} = {q_{0}, q_{2}} = C$ .

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

Accepting states = those whose subset touches $F = {q_{2}}$ , i.e. $C$ and $D$ . Only $4$ of the $2^{3} = 8$ subsets are reachable.

Exercise 2.2

Using the ε-NFA below over $Σ = {a}$ , compute the DFA start state, then trace the string $aa$ . States ${0, 1, 2, 3}$ , start $0$ , final ${3}$ : $δ_{N} (0, ε) = {1}$ , $δ_{N} (1, a) = {2}$ , $δ_{N} (2, ε) = {3}$ , $δ_{N} (3, a) = {2}$ .

Recall Solution

Start: $q_{0}^{'} = ECLOSE ({0}) = {0, 1}$ (ε-edge $0 \to 1$ ; from $1$ none). Call $A = {0, 1}$ .

Read first $a$ from $A$ : $MOVE ({0, 1}, a) = {2}$ (only $1$ has an $a$ -edge). Then $ECLOSE ({2}) = {2, 3}$ (ε-edge $2 \to 3$ ). So $A a B = {2, 3}$ .

Read second $a$ from $B$ : $MOVE ({2, 3}, a) = {2}$ (only $3$ has an $a$ -edge; $2$ has none). $ECLOSE ({2}) = {2, 3} = B$ . Self-loop $B a B$ .

Trace: $A a B a B$ . Is $B$ accepting? $B \cap {3} = {3} \neq = \emptyset$ → yes. So $aa$ is accepted. (This DFA accepts $a^{+}$ .)

Level 3 — Analysis

Exercise 3.1

An NFA has $n = 3$ states, yet its subset-construction DFA has only $3$ reachable states, not $2^{3} = 8$ . Explain in one sentence what property of the NFA guarantees fewer than $2^{n}$ reachable subsets, and give the exact count $2^{n}$ for $n = 3$ .

Recall Solution

$2^{3} = 8$ is the ceiling; reachability is what actually decides the count. Property: only subsets that appear as $ECLOSE (MOVE (\cdot))$ starting from $q_{0}^{'}$ are ever created — if the NFA's branching never produces certain combinations of states, those subsets are unreachable and are simply never generated. The blow-up to the full $8$ happens only when the NFA can, for each subset, force the DFA into it.

Exercise 3.2

Consider the classic " $k$ -th symbol from the end is $a$ " language over ${a, b}$ . It is a standard result that this language needs an NFA of $k + 1$ states, while its minimal DFA needs $2^{k}$ states. For $k = 3$ : how many states does the compact NFA have, and how many states does the exponentially-blown-up minimal DFA have?

Recall Solution

NFA states: $k + 1 = 3 + 1 = 4$ (one state to "guess" the marked position, then $k$ more to count $a, b, \dots$ to the end — the standard compact NFA for this language). Minimal DFA states: $2^{k} = 2^{3} = 8$ . Why the exponential gap is real here: to decide the $k$ -th-from-end symbol, the DFA must remember the last $k$ symbols exactly. There are $2^{k}$ distinct length- $k$ windows, and every pair of them can be told apart by some continuation — so each is a genuinely different Myhill–Nerode class (see DFA Minimization — Myhill–Nerode) and none can be merged. This is the textbook example showing that subset construction's $2^{n}$ blow-up can genuinely be forced.

Exercise 3.3

The DFA from Worked Example 2 (parent note) accepts $a^{+}$ . Suppose a student claims the same DFA also accepts the empty string $ε$ . Refute this using the accept condition, showing the exact intersection.

Recall Solution

On input $ε$ the DFA stays in its start state $A = {0, 1}$ (it reads no symbols). Accept test: $A \cap F = {0, 1} \cap {2} = \emptyset$ . Since the intersection is empty, $A$ is not accepting → $ε$ is rejected. The claim is false. The language is $a^{+}$ , not $a^{*}$ ; $a^{*}$ would require $2 \in ECLOSE ({0})$ , which it is not.

Level 4 — Synthesis

Exercise 4.1

From the regular expression $(a ∣ b)^{*} ab$ (all strings over ${a, b}$ ending in $ab$ ), build an NFA by Thompson's idea (states ${0, 1, 2}$ ), then fully convert it to a DFA. Use this NFA: start $0$ , final ${2}$ , no ε: $δ_{N} (0, a) = {0, 1}$ , $δ_{N} (0, b) = {0}$ , $δ_{N} (1, b) = {2}$ , and $δ_{N} (2, \cdot) = \emptyset$ . Build the DFA table and state its accepting states.

Recall Solution

Start: $q_{0}^{'} = {0} = A$ (no ε).

$A = {0}$ :

$a$ : ${0, 1} = B$ .
$b$ : ${0} = A$ .

$B = {0, 1}$ :

$a$ : $δ_{N} (0, a) \cup δ_{N} (1, a) = {0, 1} \cup \emptyset = {0, 1} = B$ .
$b$ : $δ_{N} (0, b) \cup δ_{N} (1, b) = {0} \cup {2} = {0, 2} = C$ .

$C = {0, 2}$ :

$a$ : ${0, 1} \cup \emptyset = {0, 1} = B$ .
$b$ : ${0} \cup \emptyset = {0} = A$ .

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

Sanity trace of $aab$ : $A a B a B b C$ → accept (ends in $ab$ ). ✔ Trace $aba$ : $A a B b C a B$ → reject (ends in $a$ ). ✔ Accepting states: ${C}$ . See Regular Expressions to NFA — Thompson's construction for the NFA build step.

Exercise 4.2

Convert this ε-NFA over $Σ = {a, b}$ fully. States ${0, 1, 2}$ , start $0$ , final ${2}$ : $δ_{N} (0, ε) = {1}$ , $δ_{N} (1, a) = {1}$ , $δ_{N} (1, b) = {2}$ , $δ_{N} (2, b) = {2}$ . Give the DFA table and accepting states.

Recall Solution

Start: $ECLOSE ({0}) = {0, 1} = A$ .

$A = {0, 1}$ :

$a$ : $MOVE = δ_{N} (0, a) \cup δ_{N} (1, a) = \emptyset \cup {1} = {1}$ ; ECLOSE $= {1} = B$ .
$b$ : $MOVE = \emptyset \cup {2} = {2}$ ; ECLOSE $= {2} = C$ .

$B = {1}$ :

$a$ : ${1}$ ; ECLOSE $= {1} = B$ .
$b$ : ${2}$ ; ECLOSE $= {2} = C$ .

$C = {2}$ :

$a$ : $MOVE = \emptyset$ → dead state $\emptyset = D$ .
$b$ : ${2} = C$ .

$D = \emptyset$ : on $a, b$ → $\emptyset = D$ (trap).

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

Language: $a^{*} b b^{*} = a^{*} b^{+}$ . Accepting: ${C}$ ; the dead state $D$ appears because $C$ dies on $a$ .

Level 5 — Mastery

Exercise 5.1

The " $2$ nd symbol from the end is $a$ " NFA over ${a, b}$ : states ${q_{0}, q_{1}, q_{2}}$ , start $q_{0}$ , final ${q_{2}}$ , $δ_{N} (q_{0}, a) = {q_{0}, q_{1}}$ , $δ_{N} (q_{0}, b) = {q_{0}}$ , $δ_{N} (q_{1}, a) = {q_{2}}$ , $δ_{N} (q_{1}, b) = {q_{2}}$ . This is the tight-blow-up family with $k = 2$ , whose minimal DFA has $2^{k} = 4$ states. Convert it fully and confirm the reachable subset DFA also has exactly $4$ states. Give the table, then read the state diagram below.

Recall Solution

Start: ${q_{0}} = A$ .

$A = {q_{0}}$ :

$a$ : ${q_{0}, q_{1}} = B$ .
$b$ : ${q_{0}} = A$ .

$B = {q_{0}, q_{1}}$ :

$a$ : $δ_{N} (q_{0}, a) \cup δ_{N} (q_{1}, a) = {q_{0}, q_{1}} \cup {q_{2}} = {q_{0}, q_{1}, q_{2}} = C$ .
$b$ : ${q_{0}} \cup {q_{2}} = {q_{0}, q_{2}} = D$ .

$C = {q_{0}, q_{1}, q_{2}}$ :

$a$ : ${q_{0}, q_{1}} \cup {q_{2}} \cup \emptyset = {q_{0}, q_{1}, q_{2}} = C$ .
$b$ : ${q_{0}} \cup {q_{2}} \cup \emptyset = {q_{0}, q_{2}} = D$ .

$D = {q_{0}, q_{2}}$ :

$a$ : ${q_{0}, q_{1}} \cup \emptyset = {q_{0}, q_{1}} = B$ .
$b$ : ${q_{0}} \cup \emptyset = {q_{0}} = A$ .

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

Exactly $4$ reachable states — matching the minimal-DFA bound $2^{k} = 2^{2} = 4$ . Both $C, D$ are accepting (each contains $q_{2}$ ). Trace $ba$ : $A b A a B$ → reject (2nd-from-end of "ba" is "b"). Trace $ab$ : $A a B b D$ → accept (2nd-from-end is "a"). ✔

Figure — NFA to DFA conversion — subset construction

Exercise 5.2

Verify the accept-condition edge case: an NFA whose start state is also final, e.g. start $=$ final $= q_{0}$ , with $δ_{N} (q_{0}, a) = {q_{0}}$ . Convert and determine whether the DFA accepts $ε$ .

Recall Solution

Start: $ECLOSE ({q_{0}}) = {q_{0}} = A$ (no ε). Accept test on $A$ : $A \cap F = {q_{0}} \cap {q_{0}} = {q_{0}} \neq = \emptyset$ → $A$ is accepting. Since the start state is accepting, the DFA accepts $ε$ (empty input never leaves the start). Transition: $A a A$ . Language $= a^{*}$ , which includes $ε$ . This shows the general rule: $ε \in L (D)$ iff $q_{0}^{'} \cap F \neq = \emptyset$ — the start subset touches a final state.

Exercise 5.3

Degenerate NFA: start $q_{0}$ , final ${q_{1}}$ , but $q_{1}$ is unreachable (no edges into it), and $δ_{N} (q_{0}, a) = {q_{0}}$ , $δ_{N} (q_{0}, b) = {q_{0}}$ . Convert and state $L (D)$ .

Recall Solution

Start: $ECLOSE ({q_{0}}) = {q_{0}} = A$ (no ε).

$A = {q_{0}}$ :

$a$ : $MOVE = {q_{0}}$ ; ECLOSE $= {q_{0}} = A$ .
$b$ : $MOVE = {q_{0}}$ ; ECLOSE $= {q_{0}} = A$ .

DFA state	on $a$	on $b$	accept?
$A = {q_{0}}$ (start)	$A$	$A$	no

Only the single DFA state $A$ is reachable. Accept test: $A \cap {q_{1}} = {q_{0}} \cap {q_{1}} = \emptyset$ → not accepting. $L (D) = \emptyset (the empty language) .$ Why: although $q_{1}$ is a declared final state, no reachable subset ever contains it, so nothing is ever accepted. Unreachable NFA finals contribute nothing — and $\emptyset$ is itself a perfectly valid regular language (see Closure Properties of Regular Languages).

Recall Quick self-check reveals

Max DFA states for $n = 4$ ? ::: $2^{4} = 16$ . Minimal DFA states for the " $3$ rd-from-end is $a$ " language ( $k = 3$ )? ::: $2^{k} = 8$ ; the compact NFA has $k + 1 = 4$ . Does an NFA with start = final accept $ε$ after conversion? ::: Yes — the start subset touches $F$ . Where do you send a transition whose MOVE is empty? ::: To the dead/trap state $\emptyset$ , which self-loops and rejects.

Connections

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