When two teams must keep independently written badge acceptors in agreement forever, what does adopting the canonical minimal machine as the shared specification cost?

Two firmware teams own two door controllers that must open on exactly the same badge sequences, forever, across revisions neither team coordinates closely. Someone proposes that the canonical minimal acceptor becomes the shared specification. It is a good proposal with a specific set of costs, and a lead is expected to name both sides. ## What uniqueness actually buys For a fixed language, the minimal complete deterministic acceptor with all states reachable is **unique up to renaming of states**. Two correct minimizations cannot differ in shape — only in what the states are called. That turns an open-ended comparison into a decidable identity check: 1. Trim unreachable states from each machine, then minimize each by partition refinement. 2. Walk both machines from their start states in lockstep, pairing states as you meet them. 3. A pairing that contradicts an earlier one, or a pair disagreeing on acceptance, means the languages differ; completing the walk means the two machines are the same up to renaming. The payoff is not merely that the check exists. It is that the answer is an **object**, not an argument: a canonical machine can be stored, reviewed, versioned and regenerated, and a disagreement produces a concrete separating badge sequence rather than a debate about diagrams. ## The costs, in the order they bite - **Readability.** Minimization merges states that behave identically, and behaviourally identical states often carry different engineering meanings. `no valid scan yet` and `no valid scan yet, but an invalid one was logged` collapse into one state — and the second existed because someone wanted to light an indicator. The canonical machine cannot hold that distinction, because it is invisible to acceptance. - **Diff instability.** Canonical form is a function of the whole language. Adding one rule about a re-scan window can renumber and reshape the entire machine, so a one-line specification change can produce a diff that touches every row of the table. Review effort does not scale with the size of the change. - **Minimality is not a shipping requirement.** A real controller carries states for timers, logging, hardware sequencing and diagnostics. Those extra states are not a defect. Demanding that the shipped machine be minimal turns a comparison tool into a design constraint nobody asked for. - **The contract is narrow.** Two acceptors that agree as acceptors are guaranteed to agree on exactly one thing: which sequences are accepted. They may differ in what they emit while running, how long they take, what they log, and what they do on inputs outside the alphabet. This is the trap most worth naming out loud, because `equivalent` sounds much stronger than it is. ## The shape that usually wins | Decision | Recommendation | Why | |---|---|---| | Source of truth for engineers | The readable machine with named modes | Debuggability and logging survive | | Artefact compared across teams | The derived canonical minimal machine | Unique up to renaming, mechanically checkable | | When the comparison runs | In an automated check on every change | Nobody remembers to trim and minimize by hand | | What the check reports | The separating sequence when they differ | A reproducible test case, not a verdict | | What else is specified | Outputs and timing, separately | Acceptance says nothing about them | In other words: treat the canonical machine as a **compiled artefact**, not as a source file. Hand-maintaining a minimized table is where this idea goes wrong most often, because the first edit made under time pressure de-minimises it silently and the canonical property is lost exactly when it was needed. ## One boundary worth stating The uniqueness result is specific to deterministic machines. There is no corresponding canonical smallest nondeterministic acceptor to compare against, so a team that keeps a nondeterministic description as its source has to determinise before the canonical form exists at all. That is a reason to make determinisation part of the pipeline, not a reason to argue about which description is nicer to read. ## How to answer this in an interview Lead with what uniqueness buys, because that is the point of canonicalisation. Then name at least two costs that a team actually feels — lost mode names and unstable diffs are the two that always show up. Finish with the boundary of the contract: acceptance only. A candidate who presents minimization purely as `fewer states is better` has missed that the state count was never the goal.