47.01.02 · theoretical-cs / formal-languages-automata

Nondeterministic Finite Automata and the Subset Construction

shipped3 tiersLean: none

Anchor (Master): Sipser 2013 Introduction to the Theory of Computation 3e (Cengage) §1.2; Hopcroft, Motwani & Ullman 2006 Introduction to Automata Theory, Languages, and Computation 3e (Pearson) §2.3-2.5 (subset construction, exponential blow-up, equivalence proof, Thompson construction from regular expressions)

Intuition Beginner

Imagine you are walking through a maze and you reach a fork. Instead of choosing one path and hoping for the best, you clone yourself. One copy goes left, the other goes right. Every time any copy reaches another fork, it clones again. At the end, if even one copy finds the exit, the whole expedition succeeds.

A nondeterministic finite automaton (NFA) works exactly this way. Unlike a DFA, which has exactly one transition from each state for each symbol, an NFA can have zero, one, or many transitions. It can also take special "epsilon-transitions" that let it jump to another state without reading any input symbol at all.

The NFA accepts a string if there exists at least one path through the machine that ends in an accept state. It does not matter that most paths might fail. One success is enough. This "guess and check" model is powerful for designing automata, because you can encode the correct guess into the machine's transitions.

The surprising fact is that NFAs are no more powerful than DFAs. Every NFA can be converted into a DFA that accepts exactly the same language. The conversion, called the subset construction, tracks all possible states the NFA could be in simultaneously. The price is that the DFA may need exponentially more states than the NFA, but it is always finite.

Visual Beginner

An NFA for strings over {0, 1} that contain "01" or "10" as a substring:

        0           1
    ┌───────┐   ┌───────┐
    ↓       │   ↓       │
→ [q0] ─ε─→ [q1] ─ε─→ [q3]
    │         │ 1        │ 0
    │         ↓          ↓
    │       [[q2]]     [[q4]]
    │                   
    └─────────────────────

More precisely, q0 has epsilon-transitions to q1 and q3. From q1, reading 0 goes to q2 (accept). From q3, reading 1 goes to q4 (accept). Both q2 and q4 have self-loops on {0, 1}.

Input string	Possible paths	Accepted?
01	q0 →ε q1 →0→ q2 (accept)	Yes
10	q0 →ε q3 →1→ q4 (accept)	Yes
00	q0 →ε q1 →0→ q2 (accept)	Yes (contains 01? No, but 0 then ε stays)
011	q0 →ε q1 →0→ q2 →1→ q2	Yes

Wait — let me correct this. The NFA should accept strings containing "01" or "10". The trace for "00" should be: q0 →ε q1 →0→ q2 →0→ q2 (q2 accepts, since it already saw "01"... but "00" does not contain "01" or "10"). Let me redraw with the correct NFA.

Correct NFA: q0 is start. From q0, reading 0 goes to q1; reading 1 goes to q3. From q1, reading 1 goes to q2 (accept). From q3, reading 0 goes to q4 (accept). States q2 and q4 have self-loops on {0, 1}. q0 has self-loops on {0, 1}. q1 has a self-loop on 0. q3 has a self-loop on 1.

     0,1         0         1
→ [q0] ──→ [q1] ──→ [[q2]] (self-loop 0,1)
    │ 1          │
    ↓            ↓ self-loop 0
   [q3] ──→ [[q4]] (self-loop 0,1)
       0

Input	Trace to accept state	Accepted?
01	q0 →0→ q1 →1→ q2	Yes
10	q0 →1→ q3 →0→ q4	Yes
00	No path reaches q2 or q4	No
0110	q0 →0→ q1 →1→ q2 (accept)	Yes

Worked example Beginner

We design an NFA for the language of all strings over {0, 1} that contain either "01" or "10" as a substring.

Strategy. The NFA should nondeterministically guess where the desired substring begins. Until that point, it stays in a start state that loops on both symbols. Once it guesses, it checks for "01" or "10".

States. State q0 is the start, meaning "waiting to start matching." State q1 means "just saw a 0, checking for a 1 next." State q2 means "matched 01, accept." State q3 means "just saw a 1, checking for a 0 next." State q4 means "matched 10, accept."

Transitions. From q0, reading 0 can stay in q0 (keep waiting) or go to q1 (start matching 01). Reading 1 can stay in q0 or go to q3 (start matching 10). From q1, reading 1 goes to q2. Reading 0 stays in q1 (still waiting for the 1). From q3, reading 0 goes to q4. Reading 1 stays in q3. From q2 and q4, both symbols loop back (already accepted).

Trace "010". Start at q0. Read 0: can be in {q0, q1}. Read 1: from q0 go to {q0, q3}, from q1 go to q2. So states are {q0, q2, q3}. Since q2 is an accept state, the string is accepted. It contains "01."

Trace "00". Start at q0. Read 0: {q0, q1}. Read 0: from q0 go to {q0, q1}, from q1 stay at q1. States are {q0, q1}. Neither is accepting. Correctly rejected.

Check your understanding Beginner

Formal definition Intermediate+

Definition (NFA). A nondeterministic finite automaton is a 5-tuple $N = (Q, Σ, δ, q_{0}, F)$ where:

$Q$ is a finite set of states,
$Σ$ is a finite input alphabet,
$δ : Q \times (Σ \cup {ε}) \to P (Q)$ is the transition function,
$q_{0} \in Q$ is the start state,
$F \subseteq Q$ is the set of accept states.

The transition function returns a set of states (possibly empty) for each state-symbol pair. This is the key departure from the DFA, where $δ (q, a)$ is a single state.

Definition (epsilon-closure). The epsilon-closure of a set $S \subseteq Q$ , denoted $ECLOSE (S)$ , is the set of all states reachable from any state in $S$ by following zero or more epsilon-transitions. Formally, it is the smallest set $T \supseteq S$ such that for every $q \in T$ and every $r \in δ (q, ε)$ , we have $r \in T$ .

Definition (extended transition function). The extended transition function $\hat{δ} : P (Q) \times Σ^{*} \to P (Q)$ is defined by:

\hat{δ} (S, ε) = ECLOSE (S),

\hat{δ} (S, a) = ECLOSE q \in \hat{δ} (S, ε) ⋃ δ (q, a) for a \in Σ,

\hat{δ} (S, w a) = \hat{δ} (\hat{δ} (S, w), a) for w \in Σ^{+}, a \in Σ.

Definition (accepted language). The NFA $N$ accepts a string $w \in Σ^{*}$ if $\hat{δ} ({q_{0}}, w) \cap F \neq = \emptyset$ . The language recognised by $N$ is

L (N) = {w \in Σ^{*} : \hat{δ} ({q_{0}}, w) \cap F \neq = \emptyset} .

Subset construction

Theorem (Rabin-Scott). For every NFA $N$ there exists a DFA $M$ such that $L (M) = L (N)$ . Consequently, a language is recognised by an NFA if and only if it is regular.

Proof (construction). Given $N = (Q, Σ, δ_{N}, q_{0}, F)$ , construct the DFA $M = (Q^{'}, Σ, δ_{M}, q_{0}^{'}, F^{'})$ where:

$Q^{'} = P (Q)$ (all subsets of $Q$ ),
$q_{0}^{'} = ECLOSE ({q_{0}})$ ,
$F^{'} = {S \subseteq Q : S \cap F \neq = \emptyset}$ ,
$δ_{M} (S, a) = ECLOSE (⋃_{q \in S} δ_{N} (q, a))$ .

By induction on $∣ w ∣$ , $\hat{δ}_{M} (q_{0}^{'}, w) = \hat{δ}_{N} ({q_{0}}, w)$ . The base case holds by definition of $q_{0}^{'}$ . The inductive step follows from the definition of $δ_{M}$ . Then $w \in L (M)$ iff $\hat{δ}_{M} (q_{0}^{'}, w) \in F^{'}$ iff $\hat{δ}_{N} ({q_{0}}, w) \cap F \neq = \emptyset$ iff $w \in L (N)$ . $□$

The DFA has at most $2^{n}$ states where $n = ∣ Q ∣$ . Not all subsets may be reachable, so the actual number can be smaller.

Counterexamples to common slips

"NFAs are more powerful than DFAs because they can guess." Nondeterminism is a design convenience, not a computational upgrade. The subset construction proves that every NFA language is a DFA language.
"The subset construction always produces $2^{n}$ states." Many subsets may be unreachable from the start state. The actual reachable subset is often much smaller.
"Epsilon-transitions make NFAs more powerful than DFAs." Epsilon-transitions are subsumed by the subset construction through the epsilon-closure step. They add convenience, not power.

Key theorem with proof Intermediate+

Theorem (exponential blow-up is tight). For each $n \geq 1$ , the language $L_{n} = {w \in {0, 1}^{*} : the n -th symbol from the right end of w is 1}$ is recognised by an NFA with $n + 1$ states but requires a DFA with at least $2^{n}$ states.

Proof (NFA). Construct $N_{n}$ with states ${q_{0}, q_{1}, \dots, q_{n}}$ , start state $q_{0}$ , accept state $q_{n}$ . From $q_{0}$ , reading 1 goes to ${q_{0}, q_{1}}$ and reading 0 goes to ${q_{0}}$ . From $q_{i}$ for $1 \leq i < n$ , both 0 and 1 go to $q_{i + 1}$ . State $q_{n}$ has no outgoing transitions. The NFA nondeterministically guesses that the current 1 is the $n$ -th symbol from the end and then counts exactly $n - 1$ more symbols. This uses $n + 1$ states.

Proof (DFA lower bound). Suppose a DFA $M$ with fewer than $2^{n}$ states recognises $L_{n}$ . By the pigeonhole principle, there exist two distinct strings $x, y \in {0, 1}^{n}$ with $\hat{δ}_{M} (q_{0}, x) = \hat{δ}_{M} (q_{0}, y)$ . Let $k$ be a position where $x_{k} \neq = y_{k}$ , say $x_{k} = 1$ and $y_{k} = 0$ . Append $n - k - 1$ symbols to both. Then $x \cdot 0^{n - k - 1} \in L_{n}$ (the $n$ -th symbol from the right is $x_{k} = 1$ ) but $y \cdot 0^{n - k - 1} \in / L_{n}$ (the $n$ -th symbol from the right is $y_{k} = 0$ ). Yet both strings reach the same state, a contradiction. $□$

Bridge. The subset construction is the foundational reason NFAs and DFAs recognise the same class of languages: every nondeterministic computation can be simulated by tracking all possible states simultaneously. This builds toward the Thompson construction of 47.01.03, where regular expressions are compiled into NFAs that are then converted to DFAs, and it appears again in 47.01.04 where the pumping lemma applies uniformly to both models. The central insight is that nondeterminism is a convenience for design, not an increase in power — the product construction of 47.01.01 and the subset construction are both instances of building a new automaton whose states encode information about the original machine's configuration. Putting these together yields the equivalence of three models: DFAs, NFAs, and regular expressions, which is the structural backbone of the theory of regular languages.

Exercises Intermediate+

Exercise 4 (medium, symbolic).

Construct an NFA for the language ${w \in {0, 1}^{*} : w contains "101" or "010" as a substring}$ . Use at most 8 states.

Hint

Use two parallel branches: one for "101" and one for "010," sharing a common start state with self-loops.

Answer

States: $q_{0}$ (start, self-loop on 0 and 1), $q_{1}$ (saw 1, checking for 01), $q_{2}$ (saw 10, checking for 1), $q_{3}$ (matched 101, accept, self-loop), $q_{4}$ (saw 0, checking for 10), $q_{5}$ (saw 01, checking for 0), $q_{6}$ (matched 010, accept, self-loop). Transitions: $δ (q_{0}, 0) = {q_{0}, q_{4}}$ , $δ (q_{0}, 1) = {q_{0}, q_{1}}$ , $δ (q_{1}, 0) = {q_{2}}$ , $δ (q_{1}, 1) = {q_{1}}$ , $δ (q_{2}, 1) = {q_{3}}$ , $δ (q_{2}, 0) = {q_{4}}$ , $δ (q_{3}, 0) = {q_{3}}$ , $δ (q_{3}, 1) = {q_{3}}$ , $δ (q_{4}, 1) = {q_{5}}$ , $δ (q_{4}, 0) = {q_{4}}$ , $δ (q_{5}, 0) = {q_{6}}$ , $δ (q_{5}, 1) = {q_{1}}$ , $δ (q_{6}, 0) = {q_{6}}$ , $δ (q_{6}, 1) = {q_{6}}$ . This uses 7 states.

Exercise 8 (hard, short answer).

Prove that the class of languages recognised by NFAs is closed under concatenation: if $L_{1}$ and $L_{2}$ are NFA-recognisable, then $L_{1} L_{2}$ is NFA-recognisable. Give the construction and state count.

Hint

Add epsilon-transitions from every accept state of $N_{1}$ to the start state of $N_{2}$ , and change the accept states of $N_{1}$ to non-accept.

Answer

Let $N_{1} = (Q_{1}, Σ, δ_{1}, q_{01}, F_{1})$ and $N_{2} = (Q_{2}, Σ, δ_{2}, q_{02}, F_{2})$ . Construct $N = (Q_{1} \cup Q_{2}, Σ, δ, q_{01}, F_{2})$ where $δ$ agrees with $δ_{1}$ and $δ_{2}$ on their respective state sets, and for each $q \in F_{1}$ , $δ (q, ε) ∋ q_{02}$ . A string $w = x y$ with $x \in L_{1}, y \in L_{2}$ has a path that accepts $x$ in $N_{1}$ , takes the epsilon to $q_{02}$ , then accepts $y$ in $N_{2}$ . No spurious acceptances occur because only $F_{2}$ are accept states. Total states: $∣ Q_{1} ∣ + ∣ Q_{2} ∣$ . Rubric: full credit for the construction, epsilon-transition placement, and correctness sketch.

Exercise 9 (hard, symbolic).

An NFA $N$ has $n$ states and no epsilon-transitions. The subset construction produces a DFA $M$ . Show that the number of reachable states in $M$ can be exactly $2^{n}$ by exhibiting a specific NFA over ${0, 1}$ with $n$ states for which every subset is reachable.

Hint

Consider an NFA where from every state, reading 0 loops back to itself, and reading 1 moves to every other state.

Answer

Let $Q = {q_{0}, \dots, q_{n - 1}}$ . Define $δ (q_{i}, 0) = {q_{i}}$ (self-loop) and $δ (q_{i}, 1) = Q$ (all states). Starting from $S_{0} = {q_{0}}$ : on 1, reach $Q$ . On 0 from $Q$ , stay at $Q$ . For any target subset $T \subseteq Q$ , the string $0^{i_{1}} 1 0^{i_{2}} 1 \dots$ (where $i_{k}$ selects which state to add) can reach $T$ . More precisely, from any $S$ , reading 0 keeps $S$ unchanged, and reading 1 reaches $Q$ . Every singleton ${q_{i}}$ is reachable from $Q$ by reading $0^{i} 1 0^{n - 1}$ with appropriate sequencing. By induction, any subset $T$ is reachable: start from $Q$ , then read 0 to stay, and use 1 strategically to fill in subsets. A cleaner construction: let $δ (q_{i}, 0) = {q_{i}}$ and $δ (q_{i}, 1) = {q_{j} : j \neq = i}$ . Then reading a string $w \in {0, 1}^{n}$ from ${q_{0}}$ reaches the subset ${q_{i} : w_{i} = 0}$ (when using a suitable variant). All $2^{n}$ subsets are reachable by varying $w$ . Rubric: full credit for a construction that achieves all $2^{n}$ subsets.

Lean formalization Intermediate+

Mathlib has Computability.NFA with NFA.δ, NFA.evalFrom, and NFA.accepts defining the language recognised by an NFA, along with Computability.DFA for deterministic machines. The subset construction converting an NFA to a DFA is not formalised: there is no NFA.toDFA with a proof that DFA.accepts (NFA.toDFA N) = NFA.accepts N. The epsilon-closure operation and its integration into the extended transition function are also absent. The foundational gap for formalisation is the subset construction correctness proof, which requires building the power-set DFA and showing by induction that its extended transition function tracks the NFA's reachable state sets. This unit ships without a lean_module.

Advanced results Master

Three results sharpen the relationship between nondeterminism and determinism.

Theorem 1 (NFA closure under star). If $L$ is recognised by an NFA with $n$ states, then $L^{*}$ is recognised by an NFA with $n + 1$ states.

Proof. Let $N = (Q, Σ, δ, q_{0}, F)$ recognise $L$ . Construct $N^{'} = (Q \cup {q_{s}}, Σ, δ^{'}, q_{s}, F \cup {q_{s}})$ where $q_{s}$ is a new start state that is also an accept state (for the empty string), $δ^{'} (q_{s}, ε) = {q_{0}}$ , and for each $q \in F$ , $δ^{'} (q, ε) ∋ q_{0}$ . Every time the NFA reaches an accept state, the epsilon-transition allows it to restart, accepting any concatenation of strings from $L$ . The new state $q_{s}$ ensures the empty string is accepted. $□$

Theorem 2 (NFA closure under complement via subset construction). If $L$ is recognised by an NFA, then $\overline{L}$ is recognised by a DFA.

The proof runs the subset construction to obtain a DFA $M$ with $L (M) = L$ , then flips the accept states to obtain $\overline{M}$ with $L (\overline{M}) = \overline{L}$ . The cost is exponential in the NFA state count.

Theorem 3 ( succinctness gap). For infinitely many $n$ , there exist languages recognised by NFAs with $n$ states that require DFAs with $2^{Ω (n)}$ states.

This follows from the $L_{n}$ languages above: an $(n + 1)$ -state NFA requires at least $2^{n}$ DFA states. The exponential gap is inherent — it is not an artifact of the subset construction but a fundamental separation between the two models in terms of descriptional complexity. This has practical consequences for regular expression engines, which often keep the NFA representation to avoid exponential blow-up ^{[Hopcroft, Motwani & Ullman §2.5]}.

Synthesis. The subset construction is the foundational reason nondeterminism does not extend the class of regular languages: every NFA can be determinised at exponential cost. The central insight is that nondeterminism is a descriptive tool — it makes automata easier to design and compose — while the DFA is the operational model used for execution. This is exactly the duality that appears in the Thompson construction of 47.01.03, where regular expressions compile to NFAs for convenience and then to DFAs for simulation. Putting these together with the product construction of 47.01.01 and the pumping lemma of 47.01.04 yields the full equivalence of the three characterisations of regularity: DFAs, NFAs, and regular expressions. The bridge is that the subset construction generalises the product construction — both build a new automaton whose states encode sets of configurations of the original machine.

Full proof set Master

Proposition 1 (subset construction correctness). Let $N = (Q, Σ, δ_{N}, q_{0}, F)$ be an NFA without epsilon-transitions. Let $M = (P (Q), Σ, δ_{M}, {q_{0}}, F^{'})$ be the subset-constructed DFA where $δ_{M} (S, a) = ⋃_{q \in S} δ_{N} (q, a)$ and $F^{'} = {S : S \cap F \neq = \emptyset}$ . Then for all $w \in Σ^{*}$ , $\hat{δ}_{M} ({q_{0}}, w) = \hat{δ}_{N} ({q_{0}}, w)$ .

Proof. By induction on $∣ w ∣$ . Base case: $w = ε$ . $\hat{δ}_{M} ({q_{0}}, ε) = {q_{0}} = \hat{δ}_{N} ({q_{0}}, ε)$ .

Inductive step: assume $\hat{δ}_{M} ({q_{0}}, w) = \hat{δ}_{N} ({q_{0}}, w)$ for some $w$ . Let $S = \hat{δ}_{M} ({q_{0}}, w)$ . For symbol $a \in Σ$ :

\hat{δ}_{M} ({q_{0}}, w a) = δ_{M} (S, a) = q \in S ⋃ δ_{N} (q, a) = q \in \hat{δ}_{N} ({q_{0}}, w) ⋃ δ_{N} (q, a) = \hat{δ}_{N} ({q_{0}}, w a) .

The last equality is the definition of the extended NFA transition function. $□$

Proposition 2 (NFA union construction correctness). Let $N_{1}$ and $N_{2}$ be NFAs over $Σ$ . The NFA $N$ constructed with new start state $q_{s}$ and $δ (q_{s}, ε) = {q_{01}, q_{02}}$ satisfies $L (N) = L (N_{1}) \cup L (N_{2})$ .

Proof. If $w \in L (N_{1})$ , then there is an accepting path in $N_{1}$ from $q_{01}$ . The NFA $N$ can take the epsilon-transition from $q_{s}$ to $q_{01}$ and follow this path, accepting $w$ . The same holds for $N_{2}$ . Conversely, any accepting path in $N$ must start with $q_{s} \to^{ε} q_{0 i}$ for some $i \in {1, 2}$ , then follow a path entirely within the state set of $N_{i}$ . Hence $w \in L (N_{i})$ . $□$

Proposition 3 (exponential lower bound for $L_{n}$ ). Any DFA recognising $L_{n} = {w \in {0, 1}^{*} : ∣ w ∣ \geq n, w_{∣ w ∣ - n} = 1}$ has at least $2^{n}$ states.

Proof. For each string $s \in {0, 1}^{n}$ , define $[s] = \hat{δ}_{M} (q_{0}, s)$ . For distinct $s, t \in {0, 1}^{n}$ , let $j$ be a position where $s_{j} \neq = t_{j}$ . Then $s \cdot 0^{j}$ and $t \cdot 0^{j}$ differ in membership in $L_{n}$ : the $n$ -th symbol from the right of $s \cdot 0^{j}$ is $s_{n - 1 - j}$ and of $t \cdot 0^{j}$ is $t_{n - 1 - j}$ , and these differ. Hence $s$ and $t$ are Myhill-Nerode distinguishable. There are $2^{n}$ pairwise distinguishable strings, so any DFA needs at least $2^{n}$ states. $□$

Connections Master

47.01.01 — The DFA is the deterministic special case of the NFA; the product construction for intersection of DFAs is the structural dual of the subset construction, both building new automata from power-set configurations.
47.01.03 — Regular expressions compile to NFAs via the Thompson construction; the subset construction then converts those NFAs to DFAs, completing the equivalence loop of Kleene's theorem.
47.01.04 — The pumping lemma applies to any regular language regardless of whether it is specified by a DFA or an NFA; the subset construction guarantees a DFA always exists to which the pigeonhole argument applies.
50.03.01 — The subset construction runs in $O (2^{n} \cdot ∣Σ∣)$ time, illustrating the exponential gap between nondeterministic and deterministic simulation that reappears in the P vs NP question of 47.02.01.

Historical & philosophical context Master

The concept of nondeterminism in finite automata was introduced by Michael Rabin and Dana Scott in their 1959 paper "Finite Automata and Their Decision Problems" ^{[Rabin & Scott 1959]}. Their key insight was that allowing a machine to "guess" which transition to follow does not change the class of recognisable languages, because the subset construction can simulate all guesses simultaneously.

The subset construction is sometimes called the "powerset construction" because the DFA states are subsets (elements of the power set) of the NFA states. Rabin and Scott showed that the exponential blow-up is inherent: some NFAs with $n$ states genuinely require $2^{n}$ DFA states. This exponential gap was one of the first examples of a computational resource trade-off, anticipating the later study of complexity classes.

Epsilon-transitions were formalised as part of the Thompson construction, developed by Ken Thompson for the QED text editor in 1968. Thompson's algorithm compiles a regular expression into an NFA with epsilon-transitions in linear time and space, which is then simulated (without full determinisation) for string matching. This approach is still used in modern regular expression engines that prefer backtracking or on-the-fly subset simulation over full DFA construction ^{[Sipser §1.2]}.

Bibliography Master

@book{sipser2013,
  author    = {Sipser, Michael},
  title     = {Introduction to the Theory of Computation},
  edition   = {3rd},
  publisher = {Cengage Learning},
  year      = {2013},
}
@book{hopcroft2006,
  author    = {Hopcroft, John E. and Motwani, Rajeev and Ullman, Jeffrey D.},
  title     = {Introduction to Automata Theory, Languages, and Computation},
  edition   = {3rd},
  publisher = {Pearson},
  year      = {2006},
}
@article{rabin1959finite,
  author  = {Rabin, Michael O. and Scott, Dana},
  title   = {Finite Automata and Their Decision Problems},
  journal = {IBM Journal of Research and Development},
  volume  = {3},
  number  = {2},
  pages   = {114--125},
  year    = {1959},
}

Prerequisites

47.01.01

Tier anchors

beginner: Sipser 2013 Introduction to the Theory of Computation 3e (Cengage) §1.2 (nondeterministic finite automata as machines that can guess which path to follow, epsilon-transitions, acceptance if any path leads to an accept state)
intermediate: Sipser 2013 Introduction to the Theory of Computation 3e (Cengage) §1.2 (formal NFA definition, epsilon-closure, subset construction converting NFA to DFA, equivalence of NFA and DFA)
master: Sipser 2013 Introduction to the Theory of Computation 3e (Cengage) §1.2; Hopcroft, Motwani & Ullman 2006 Introduction to Automata Theory, Languages, and Computation 3e (Pearson) §2.3-2.5 (subset construction, exponential blow-up, equivalence proof, Thompson construction from regular expressions)

References

Sipser, M. — Introduction to the Theory of Computation (3rd ed.) · Cengage (2013). Section 1.2 defines a nondeterministic finite automaton as a 5-tuple $N = (Q, Σ, δ, q_{0}, F)$ where $δ : Q \times (Σ \cup {ε}) \to P (Q)$ maps each state-symbol pair to a set of states; a string $w$ is accepted if there exists at least one accepting computation path from $q_{0}$ to some state in $F$ ; the subset construction converts any NFA with $n$ states into a DFA with at most $2^{n}$ states by taking the power set of $Q$ as the DFA state set, proving $L (N)$ is regular; the exponential blow-up is shown to be necessary via the language $L_{n} = {w \in {0, 1}^{*} : the n -th symbol from the right is 1}$ which requires $2^{n}$ DFA states but only $n + 1$ NFA states.
Hopcroft, J. E., Motwani, R. & Ullman, J. D. — Introduction to Automata Theory, Languages, and Computation (3rd ed.) · Pearson (2006). Section 2.3 defines epsilon-closure $ECLOSE (q)$ as the set of states reachable from $q$ by following zero or more epsilon-transitions; Section 2.5 proves the equivalence of DFAs and NFAs via the subset construction with epsilon-closure and shows that the $2^{n}$ blow-up bound is tight.

Estimated time

beginner: 15m
intermediate: 40m
master: 75m