The table-filling algorithm computes state equivalence and DFA minimization

Replace $D$ by its reachable part using [L1]. Let $M_0$ be the set of accepting/nonaccepting pairs, and for $t\ge 0$ let $M_{t+1}$ be obtained from $M_t$ by also marking every pair $\{p,q\}$ for which some letter $a$ has $\{\delta (p,a),\delta (q,a)\}\in M_t$. Put $M:={\bigcup }_t{M}_t$.

We prove by induction on $t$ that every pair in $M_t$ has a distinguishing word of length at most $t$. For $M_0$, the empty word distinguishes every accepting/nonaccepting pair by [L2]. For the induction step, if $\{p,q\}$ is newly marked because $\{\delta (p,a),\delta (q,a)\}\in M_t$, prepend the letter $a$ to a distinguishing word for the successor pair.

Conversely, we induct on the length of a distinguishing word $x$. If $x=\epsilon$, then the pair is in $M_0$. If $x=ay$, then $y$ distinguishes $\delta (p,a)$ and $\delta (q,a)$, so the induction hypothesis puts the successor pair in some $M_t$, and the algorithm then marks $\{p,q\}$ at the next stage. Therefore a pair is marked exactly when it is distinguishable.

Unmarked pairs are therefore precisely the indistinguishable pairs, hence precisely the state-equivalent pairs by [L2]. By [L3] this is an equivalence relation, and [L4] gives an equivalent quotient DFA $Q$.

Let $E$ be any reachable DFA equivalent to $D$. Because step 1.1 replaced $D$ by its reachable part, each state class $C$ of $Q$ has a representative state $q_C$ reached in $D$ by some word $u_C$. Send $C$ to the state reached by $E$ on $u_C$. If $C\mathrm{\ne }{C}^{\mathrm{\prime }}$, then their representatives are distinguishable by step 3.1; choose a distinguishing word $x$. The words $u_{C}x$ and $u_{C^{\mathrm{\prime }}}x$ are then accepted differently by $D$, hence also by the equivalent DFA $E$, so the reached states of $E$ are distinct. Thus this map from the states of $Q$ into the states of $E$ is injective.

Therefore every reachable DFA equivalent to $D$ has at least as many states as $Q$. Since $Q$ itself is equivalent to $D$ by step 4.1, it is a minimal DFA for the same language.