NFA to DFA conversion — subset construction: Visual walkthrough

Step 1 — Two machines, one difference

WHAT. Look at the two little machines in the figure. On the left, a Non-deterministic Finite Automaton (NFA): from one room, one letter, you can be sent to several rooms — or slide for free along a dashed $ε$ -edge (an edge you cross without reading any letter). On the right, a Deterministic Finite Automaton (DFA): one room, one letter, exactly one destination, no dashed edges.

WHY. Everything on this page exists to bridge this one gap. The NFA is allowed to be in a set of rooms; the DFA is forced to be in a single room. The whole trick will be: make the DFA's single room stand for the NFA's whole set of rooms.

PICTURE. The NFA (left) shows room $q_{0}$ firing into ${q_{0}, q_{1}}$ on the letter $a$ — two arrows from one letter. The DFA (right) shows one arrow per letter. That fan-out on the left is the "many at once" we must tame.

Figure — NFA to DFA conversion — subset construction

Step 2 — The notebook idea: one DFA room = a SET of NFA rooms

WHAT. We declare, once and for all: a single state of the DFA is a set of NFA rooms. If the NFA might be standing in rooms $0$ and $1$ simultaneously, the DFA has one state literally named ${0, 1}$ .

WHY. A DFA cannot split. But a set is a single object. So "the collection of all rooms the NFA could be in" is itself one thing — and we let the DFA hold that one thing. Because these sets are drawn from the power set $P (Q)$ of all subsets, this is the subset construction.

PICTURE. The figure boxes up the NFA's three rooms and then draws a few sets of them ( ${0}$ , ${0, 1}$ , ${1, 2}$ ) as new single tiles. Each tile is one future DFA room.

$one DFA room S = a set of NFA rooms {q_{i}, q_{j}, \dots} \in all possible sets of rooms P (Q)$

Term by term: $S$ is the DFA state we are naming; the braces ${\dots}$ hold the NFA rooms it stands for; $P (Q)$ is the shelf of every subset — with $∣ Q ∣ = 3$ rooms there are $2^{3} = 8$ shelves, though we will only ever visit the reachable ones.

Step 3 — Before reading anything: the free slide (ε-closure)

WHAT. We compute where the NFA can be before it reads a single letter. Start room is $0$ . But room $0$ has a dashed $ε$ -edge to room $1$ — a free slide. So the NFA is already possibly in both $0$ and $1$ . We bundle those: $ECLOSE ({0}) = {0, 1}$ .

WHY. The dashed edges cost no input. So the instant the machine is switched on, it has silently drifted everywhere those free edges reach. If the DFA started at just ${0}$ it would forget room $1$ was reachable — and miss strings the NFA accepts. The ε-closure is the fix.

PICTURE. Watch the green flood: it starts on room $0$ , then walks the dashed edge to $1$ , and stops (room $1$ has no outgoing dashed edge). The green blob ${0, 1}$ is our DFA start state, call it $A$ .

$q_{0}^{'} = follow only free ε -edges ECLOSE (the lone start room {q_{0}}) = {0, 1} = A$

$ECLOSE (S)$ = every room reachable from $S$ using only $ε$ -edges, including $S$ itself. Here ${0}$ closes up to ${0, 1}$ .

Step 4 — Reading a letter: MOVE, then close again

WHAT. From state $A = {0, 1}$ we read the letter $a$ . Two sub-steps, in strict order:

MOVE — take a real $a$ -step from every room in $A$ . Room $0$ has no $a$ -edge; room $1$ has $δ (1, a) = {2}$ . So $MOVE ({0, 1}, a) = {2}$ .
ECLOSE — now let the result drift along free edges. Room $2$ has a dashed edge to $1$ , so $ECLOSE ({2}) = {1, 2}$ .

Combine: $δ_{D} (A, a) = {1, 2}$ . Call this new state $B$ .

WHY this order. Reading a letter is one honest step followed by any number of free slides. If you closed before moving but forgot to close after, you would land in ${2}$ and forget that the NFA immediately slides to $1$ as well — losing the $a$ -step that room $1$ later enables. MOVE-then-CLOSE, every time.

PICTURE. Orange arrow = the real $a$ -step ( $1 \to 2$ ). Green flood again = the ε-closure that pulls in room $1$ . The final blob $B = {1, 2}$ is a new tile, so we add it to the notebook as unprocessed.

$δ_{D} (S, a) = slide free after ECLOSE (one real a -step from every room in S MOVE (S, a))$

$MOVE (S, a) = ⋃_{q \in S} δ (q, a)$ — the union sign $⋃$ says "collect the targets from each room in $S$ and pool them." Then ECLOSE wraps free slides around that pool.

Step 5 — Repeat until the notebook stops growing

WHAT. State $B = {1, 2}$ is unprocessed, so read $a$ from it. MOVE: room $1$ gives ${2}$ , room $2$ has no $a$ -edge, so $MOVE ({1, 2}, a) = {2}$ . ECLOSE gives ${1, 2} = B$ again. So $B a B$ — a self-loop. No new state appears.

WHY it terminates. Every DFA state is a subset of $Q$ , and there are only $2^{∣ Q ∣} = 2^{3} = 8$ subsets. Each round either produces an old set (stop expanding down that branch) or a genuinely new one. You cannot invent new subsets forever, so the process must halt. (This is why the DFA is finite.)

PICTURE. The growing notebook: tile $A$ , arrow to tile $B$ , and $B$ looping to itself. There are no fresh tiles left to process — we are done exploring.

DFA state	reachable?	on $a$
$A = {0, 1}$ (start)	yes	$B$
$B = {1, 2}$	yes	$B$

We never listed the other $8 - 2 = 6$ subsets — they are unreachable from the start, so they simply do not exist in our DFA. (Trap: don't generate all $2^{n}$ up front.)

Step 6 — Which tiles are accepting?

WHAT. A DFA state is accepting exactly when its set contains at least one NFA accepting room. Our final room is $F = {2}$ .

$A = {0, 1}$ : does it contain $2$ ? No — ${0, 1} \cap {2} = \emptyset$ → reject.
$B = {1, 2}$ : does it contain $2$ ? Yes — ${1, 2} \cap {2} = {2} \neq = \emptyset$ → accept.

WHY "contains", not "equals". The NFA succeeds if any single one of its parallel paths ends in a final room. So the notebook state succeeds as soon as it touches $F$ — one accepting room on the list is enough. Demanding the whole set equal ${2}$ would wrongly reject the accepting state ${1, 2}$ .

PICTURE. Room $2$ glows as the NFA's exit. Any tile whose set overlaps that glow gets a double-ring (accepting). $B$ lights up; $A$ stays plain.

$F^{'} = {S : the set touches at least one final room S \cap F \neq = \emptyset}$

$S \cap F$ is the overlap of a DFA-tile with the NFA's finals; the condition $\neq = \emptyset$ ("is not empty") is the "touches" test.

Step 7 — The degenerate case: the empty tile $\emptyset$

WHAT. Suppose MOVE ever returns nothing — say we read a letter no live room can handle. Then $ECLOSE (\emptyset) = \emptyset$ , the empty set. This is a legitimate DFA state: the notebook is blank, no NFA room is alive.

WHY it matters. A DFA's transition function must be total — defined for every state and every letter. If we left it undefined, the machine would jam. Instead $\emptyset$ is the dead/trap state: once empty, every letter keeps it empty ( $\emptyset a \emptyset$ ), and since $\emptyset \cap F = \emptyset$ it is never accepting. It swallows all doomed strings.

PICTURE. A grey empty tile with self-loops on every letter, marked "reject forever." (In our example every MOVE stayed non-empty, so $\emptyset$ is unreachable and we may omit it — but you must know it exists.)

The one-picture summary

WHAT. One diagram, whole derivation: NFA on the left, the pipeline (ECLOSE start → MOVE-then-ECLOSE per letter → touch-test for accept) in the middle, the finished DFA on the right.

Recall Feynman: the whole walkthrough in plain words

A magic robot can stand in many rooms at once and slip through free doorways without spending a letter. A plain robot can't split — so we hand it a notebook.

First, before reading anything, the plain robot writes down every room the magic robot could already be in after slipping through free doorways — that's the start page ( $ECLOSE$ of the start room). Then each time it reads a letter, it does the same two things: take one honest step from every room on the current page (MOVE), then slip through all the free doorways again (ECLOSE). That gives the next page. It keeps discovering pages until no new page appears — which must happen, because there are only finitely many possible lists of rooms. Finally, it circles every page that mentions an exit room: if any listed room is an exit, that page means "Accepted." And if a page ever goes blank, that's the dead-end page that just says "no" forever. That filled notebook is the DFA.

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
Power Set and Subsets
DFA Minimization — Myhill–Nerode
Closure Properties of Regular Languages
Pumping Lemma for Regular Languages