= Solution
\b[The minimal <deterministic finite automaton> is unique up to an <isomorphism> preserving the initial state, transitions and accepting states.] We use complete <deterministic finite automata> over the fixed <alphabet>; the PDF's abbreviation FDA has this meaning. State names themselves cannot be unique.
For <words> $u,v\in\Sigma^*$, introduce the <Myhill-Nerode equivalence>
$$
u\sim_Lv\quad\Longleftrightarrow\quad\forall w\in\Sigma^*\;\bigl(uw\in L\iff vw\in L\bigr).
$$
It is an <equivalence relation>, and appending the same letter to equivalent <words> preserves it: a suffix $w$ after $ua$ is the suffix $aw$ after $u$. Since $L$ is a <regular language>, take any recognizing <deterministic finite automaton>. Words reaching the same state are equivalent, since every further suffix gives the same computation. Thus $\sim_L$ has finite index.
The <canonical residual automaton> has one state $[u]$ for each class, initial state $[\epsilon]$, transition $[u]\xrightarrow{a}[ua]$, and accepting states those with $u\in L$. These choices are well-defined by <Myhill-Nerode equivalence>. Induction on the input length shows that reading $u$ reaches $[u]$, so the <deterministic finite automaton> recognizes $L$, and all its states are <accessible states of a deterministic finite automaton>. The same state can be described by the <left quotient of a formal language>
$$
u^{-1}L=\{w:uw\in L\}.
$$
Two states are different precisely when some suffix distinguishes their acceptance behavior.
Every recognizing <deterministic finite automaton> has at least as many states as there are classes: pick a representative from each class; two different representatives cannot reach the same state. The <canonical residual automaton> attains this bound, and therefore is a <minimal deterministic finite automaton>.
For uniqueness, let $\mathcal A$ be any <minimal deterministic finite automaton>. All its states are accessible, since removing inaccessible states leaves a complete recognizing <deterministic finite automaton> with fewer states. Map a state reached by $u$ to $[u]$. This is well-defined because two <words> reaching the same state are equivalent. It is surjective because every class has a representative. Both sets have the minimal number of states, so it is a <bijection>. It preserves the initial state and transitions by construction, and preserves accepting states by taking the <empty word> as the suffix. This is the required <isomorphism> with the <canonical residual automaton>, proving
$$
\boxed{\text{minimal number of states}=|\Sigma^*/{\sim_L}|,\quad\text{uniqueness up to isomorphism}.}
$$
The <empty word> is included throughout, and empty or universal <regular languages> have the corresponding one-state complete <deterministic finite automata>.
Back to article page
