Minimization & Equivalence

Two teams ship door-controller firmware, and both claim their controller opens on exactly the same badge sequences. One machine has six states, the other three. Comparing them state by state means nothing until you have a definition of when two states really are the same state. That definition is distinguishability, and every minimization result is built on it. ## A state is its future, not its past A deterministic finite acceptor is a finite set of states, an input alphabet, a total transition function, one start state and a set of accepting states. The moment the machine enters a state, the prefix that took it there is gone — the current state is the machine's entire memory. So everything a state can still contribute to the verdict is answered by one question: **for each possible remaining input, does the run end in an accepting state?** That gives the definition. States `p` and `q` are **distinguishable** when there exists a string `w` such that reading `w` from `p` ends accepting and reading `w` from `q` does not, or the reverse. Such a `w` is a **distinguishing suffix**, or witness — it is concrete evidence you can show in a review. When no string whatsoever separates them, `p` and `q` are **equivalent**, and merging them leaves the accepted language untouched. Two consequences fall straight out: - The **empty suffix** distinguishes any accepting state from any non-accepting one. Every minimization procedure therefore begins by separating those two groups. - The **prefixes that reached the states are irrelevant**. Two states arrived at by completely different badge histories are the same state if their futures agree. This is the point candidates most often miss. ## Myhill-Nerode: the language fixes the state count The **Myhill-Nerode theorem** applies the same relation to strings instead of states. Call two input strings `x` and `y` equivalent for a language `L` when, for every suffix `w`, `xw` is in `L` exactly when `yw` is. The theorem says a language is regular precisely when this relation has finitely many classes, and that the minimal deterministic acceptor has **one state per class**. So the minimum number of states is decided by the language, before anyone writes firmware. An implementation may carry extra states; it can never carry fewer. That is why minimization is a canonicalisation, not an optimisation trick. ## Worked example: two badge controllers Take the language of badge sequences that unlock a door once two valid scans have been seen, over the alphabet `v` (valid scan) and `x` (rejected scan). One team's firmware has six states: `A` (start, no valid scan yet), `D` (no valid scan yet, but an invalid one has been logged), `B` and `C` (one valid scan seen, reached by two different paths), and `E` and `F` (unlocked, accepting). | Pair | Distinguishing suffix | Verdict | |---|---|---| | `A` vs `B` | `v` | one further valid scan unlocks from `B` only — distinguishable | | `B` vs `E` | empty string | `E` accepts, `B` does not — distinguishable | | `A` vs `D` | none exists | equivalent: both still need two valid scans | | `E` vs `F` | none exists | equivalent: both accept every continuation | The six-state machine therefore collapses to three: still-need-two, still-need-one, unlocked. The other team's three-state firmware is the same machine with different state names. ## Finding the witnesses mechanically You do not have to guess suffixes. Mark every pair whose members disagree on acceptance, then repeatedly mark any pair that some letter sends to an already-marked pair, recording that letter in front of the shorter witness. When a pass marks nothing new, the unmarked pairs are exactly the equivalent ones, and each marked pair carries a concrete separating string. This is the pairwise view of the same fact that partition refinement computes block by block. ## Traps this catches in review - Arguing that two states differ because different badge histories reach them. Histories are not observable to the machine. - Checking only acceptance status. Two non-accepting states can still be miles apart — the witness is just longer than the empty string. - Assuming a bigger machine accepts more. Six states and three states here accept exactly the same set of sequences; the extra states are duplicated futures. - Declaring equivalence after checking one letter. Equivalence is a claim about every suffix, which is why the marking loop runs to a fixed point.