Foundations — NFA to DFA conversion — subset construction

Before you can read the parent note, you must own every symbol it throws at you. Below, each item is built in order: plain words → the picture → why the topic needs it. Nothing later uses anything not defined earlier.

1. A "state" — the dot in a machine

Why the topic needs it: the entire construction is about which dots the machine could be sitting on. If you don't picture states as dots you sit on, "set of states" means nothing.

2. The letters $a$, $b$ and the alphabet $\Sigma$

Why the topic needs it: every transition is "on reading letter $a$…". The DFA we build must give an answer for each letter in $\Sigma$ — no letter left undefined.

3. The empty move $\epsilon$ (epsilon)

Why the topic needs it: because the NFA can silently slide along these free edges before and after every real letter, the DFA must chase all such slides. This is the whole reason ECLOSE (item 9) exists.

4. The arrow / transition and $\delta$ (delta)

Why the topic needs it: $\delta$ is the machine. Converting NFA→DFA is really rewriting one rulebook (${\delta }_N$) into another (${\delta }_D$).

5. The crucial difference: one answer vs. a set of answers

This is the heart of why the topic is hard, so it gets its own figure.

Why the topic needs it: an NFA on $\{q_1,q_3\}$ reading $a$ might land on $\{q_2,q_3,q_5\}$ — a set. A DFA cannot sit on a set of dots. The fix (the topic's big idea): invent a new single dot whose NAME is that set.

6. Sets, $\in$, $\cup$, $\varnothing$, and $\cap$

The construction lives entirely in the language of sets. Four symbols carry it.

Why the topic needs each:

• $\cup$ appears in MOVE: gather next-dots from every current dot.
• $\varnothing$ is the DFA's dead/trap state (no dots alive → reject forever).
• $\cap$ appears in the accept test $S\cap F\ne \varnothing$ ("does the bag touch a final dot?").

7. The power set $\mathcal{P}(Q)$ and why $2^n$

Why the topic needs it: DFA states are exactly the bags in $\mathcal{P}(Q)$. This is why the construction is called the subset (powerset) construction, and why it always terminates: there are only $2^n$ possible DFA states, a finite number. See Power Set and Subsets.

8. Start dot $q_0$ and final dots $F$

Why the topic needs it: the DFA's start becomes $\text{ECLOSE}(\{q_0\})$ (item 9), and a DFA bag is accepting iff it touches $F$: $S\cap F\ne \varnothing$.

9. ECLOSE and MOVE — the two derived operations

Everything above now assembles into the two operations the parent note runs.

Why this order: you can only cross an $\epsilon$-edge after arriving somewhere by the real letter. Closing before but not after is the parent note's Mistake 2.

The prerequisite map

Equipment checklist

Test yourself — cover the right side and answer aloud.

Connections

• Parent topic
• Finite Automata — DFA basics
• Finite Automata — NFA and ε-NFA
• Power Set and Subsets
• Regular Expressions to NFA — Thompson's construction
• DFA Minimization — Myhill–Nerode