Motivation
Two states with different names need not represent different information. If every possible continuation produces the same accept-or-reject answer from both states, a reader of the machine can safely identify them. Conversely, one distinguishing continuation proves that the states cannot be identified. This section turns that observation into both a canonical construction and a finite algorithm. The automata here are deterministic and complete; missing transitions must first be sent to a rejecting sink.
Definitions
Definition 1.1.1
(Residual language and prefix equivalence)
Fix a finite alphabet and a language . The residual of after a word is . Two words satisfy when .
Definition 1.1.2
(State equivalence, reachability and minimality)
In a DFA, two states are equivalent if they accept exactly the same continuations. A state is reachable if some word takes the initial state to it. Minimality means fewest states among complete DFAs recognizing .
The right-congruence property follows directly: if , then for each letter , since exactly when . Notice that and need not themselves be in ; the residual tests every continuation, including .
Theorems
Theorem 1.1.3
(Myhill–Nerode theorem)
A language is recognized by a finite DFA if and only if has finitely many classes. In that case the DFA whose states are those classes, initial state , transition , and accepting states with is a smallest complete DFA for . Every smallest complete DFA for is isomorphic to it as a pointed, labeled, accepting-state automaton.
Theorem 1.1.4
(Partition refinement)
Given a finite complete DFA, delete unreachable states. Start with whichever of the accepting and nonaccepting state sets are nonempty. Repeatedly split a block whenever two of its states have transitions on some letter into different current blocks. When no split remains, the blocks are exactly the state-equivalence classes. The quotient DFA is minimal for the original language.
Proof sketch or proof idea
Proof
(Residual classes give the minimal DFA)
Suppose first that a DFA recognizes . If reading and reaches the same state, every continuation has the same outcome, so . Hence there are at most as many residual classes as states. Conversely, when there are finitely many classes, the displayed construction is well-defined by right congruence; acceptance is well-defined because is a possible continuation. Induction on shows that the state after is . Thus it recognizes .
Any DFA for must reach different states on words in different classes, giving the lower bound. The constructed machine attains it. If another machine attains it, all its states are reachable: otherwise deleting unreachable states would produce a smaller machine. Its map sending the state reached by to is well-defined, surjective and, by equal finite cardinalities, bijective. It preserves the start state, transitions and acceptance. This proves uniqueness up to renaming, not literal equality of state names.
Proof
(Stable partitions are the equivalence classes)
For refinement, initially no block contains both an accepting and a rejecting state, so equivalent states are not separated. If a split separates on , then their successor blocks were already separated; inductively some suffix distinguishes the successors, so distinguishes . Thus equivalent states are never split. At termination, states in a common block have successors in a common block on every letter and agree on acceptance. Induction on continuation length now shows they are equivalent. Each strict split increases the number of blocks, at most the number of reachable states, so the process terminates. The quotient recognizes the same language by induction on input length, and its distinct states are distinguishable. It is consequently minimal by the first theorem.
Proof X-ray
Why every suffix matters
Agreement on the empty continuation checks only current acceptance. The refinement step checks one additional initial letter and then relies on an arbitrary suffix. The induction covers every finite continuation, even though the algorithm stores only finitely many blocks.
The hypotheses enter in three places. Completeness of the transition function makes defined for every state and word, so every continuation can be tested. Finiteness of the state set bounds the number of splits, which is why the process stops. The key move is the witness bookkeeping: a split is never made without a suffix that really separates the two states, so an equivalent pair is never separated, and stability supplies the converse. Dropping completeness would leave some continuations untested.
Worked examples
Worked example 1.1.5
(Even parity)
Over let contain words with an even number of ones. There are two residuals: after an even prefix the continuation needs even parity, and after an odd prefix it needs odd parity. They differ on . The minimal machine therefore has two states; loops and swaps them, with the even state initial and accepting.
Worked example 1.1.6
(One refinement separates two rejecting states)
Consider alphabet and states , initial , only accepting , and transitions , , . All states are reachable. Initially the blocks are and . The first block splits because goes to the former and to the latter. The three singleton blocks are stable. The suffix distinguishes from , and distinguishes either from .
Worked example 1.1.7
(A language needing infinitely many states)
For , the prefixes and for distinct nonnegative are distinguished by : but . Thus there are infinitely many residuals and no finite DFA recognizes . This proof chooses a distinguishing suffix for each pair rather than applying the pumping lemma.
Common mistakes
Counterexample mode
Same present answer is not the same state
In the three-state example and both reject the empty continuation, but is accepted from and rejected from . Combining them solely because both currently reject changes the language.
Common mistake
(Skipping the removal of unreachable states)
Removing unreachable states is essential to minimizing a given machine. Merging equivalent reachable states without removing an unreachable isolated state can leave a nonminimal result.
Conversely, a quotient block may contain several states without losing information: its transitions are well-defined precisely because the final partition is stable.
Reading and implementing the refinement
It helps to view refinement as a sequence of increasingly demanding experiments. Initially two states remain together when they agree about the empty continuation. After one simultaneous refinement, states also agree on all continuations of length one. After rounds they agree on continuations of length at most . This assertion follows by induction: a continuation of length at most is either empty or has the form , where has length at most . To agree on all such strings, the -successors must agree through round for every .
This interpretation assumes each round is performed simultaneously from the preceding partition. An implementation may instead split blocks one at a time; it reaches the same stable partition, but its intermediate partitions need not coincide with the length-indexed rounds. In either implementation the algorithm must keep checking every letter after a split, because a new distinction between successors can reveal an older distinction between their predecessors.
For a small automaton one can construct a table of unordered pairs of reachable states. Mark every pair whose members disagree on acceptance, using as a witness. Whenever an unmarked pair has -successors already marked with witness , mark it with witness . Continue until no pair can be marked. The unmarked pairs are equivalent by the same stable-partition argument. Witnesses are useful when checking an implementation: they demonstrate a concrete input on which merging a particular pair fails. They are not necessarily shortest unless pairs are processed in appropriate length order.
Worked example 1.1.8
(Refinement propagates backwards)
Take four unary states , with initial, the only accepting state, and moving each to for while loops. All are reachable. The initial partition is . One simultaneous round separates , whose successor accepts, from . The next separates from , because their successors now lie in distinct blocks. The suffix distinguishes and : it reaches from the former and from the latter. All four states are necessary.
The quotient is defined for each original transition by . Stability ensures that the result does not depend on the chosen representative . For every word , induction gives . Thus the quotient does more than retain acceptance of complete inputs from the start: it preserves the behavior of every original state on every future input. This explains why it is legitimate to merge the states during the computation, rather than only after a full word has been read.
There is a useful distinction between the equivalence of states in a fixed automaton and equivalence of prefixes of a language. State equivalence asks what happens when an arbitrary state is used as the starting point. Prefix equivalence asks what residual language follows a prefix from the actual start. Every reachable state corresponds to at least one prefix, and its continuation language is precisely that prefix's residual. Unreachable states have continuation languages too, but they cannot contribute new residuals reached from the actual start and therefore do not belong in the canonical minimal machine.
A language comparison
The canonical machine also provides a decision procedure for equivalence of two given complete DFAs over the same alphabet. Form their disjoint union as a transition system, refine the combined state set by acceptance and transitions, and compare the two initial states. They are in the same final block precisely when every word is accepted by both or rejected by both. Unlike minimizing each machine separately and then comparing names, this procedure does not assume any particular naming convention. A marked initial-state pair in the pair-table method supplies an explicit word witnessing inequivalence. Before combining machines whose alphabets differ, specify a common alphabet and complete the transition functions with sinks; otherwise “same language” has not yet been posed over the same domain.
For example, the language of words with an even number of ones is unchanged if a redundant state is inserted that has exactly the same accepting status and successor behavior as the original even state. Such duplication does not change any continuation language, so refinement merges the duplicate with the original whenever both are reachable. In contrast, adding a new state with a different transition on one letter may make the two states distinguishable only after several further letters. Immediate transition equality is sufficient for equivalence only when targets are already equivalent, not merely when their labels look similar.
Finite witnesses and algorithmic scope
The finite-state hypothesis matters twice in the algorithm. First, reachability can be computed by graph search: start with the initial state and repeatedly add every letter-successor of an already reached state. Because there are finitely many states, this process stops. Second, there are only finitely many possible splits of the reachable-state set. A stable partition therefore appears after finitely many changes. The proof of correctness does not require an a priori bound on the length of the shortest distinguishing word, although the finite pair table can itself produce such a witness when it marks a pair.
The theorem is a statement about all languages, including nonregular ones. Its forward implication turns a finite machine into finitely many residuals. Its reverse implication constructs a machine from finitely many residuals. To prove nonregularity by this theorem, it is enough to exhibit an infinite family of prefixes with pairwise different residuals. One does not need to list every residual or find an algorithm to calculate them. On the other hand, inspecting a few examples of distinguishable prefixes does not prove that infinitely many classes exist: the pairwise argument must work for arbitrarily many distinct indices.
Common mistake
(A few distinguished prefixes do not prove infinitely many classes)
For , checking that , and are pairwise distinguishable shows only that at least three states are needed. A nonregularity proof must give the distinguishing suffix for arbitrary , as in the worked example, so that the number of classes is not bounded.
A minimal machine is unique only after its input alphabet and completeness convention have been fixed. If partial automata are allowed to reject when a transition is missing, a rejecting sink can sometimes be omitted, changing the state count. The present construction uses a total transition function, and its residual for a hopeless prefix is the empty language. That empty residual is an ordinary state whenever it is reached. Similarly, changing the alphabet can introduce new possible continuations; comparisons should make the common alphabet explicit.
As a final check, consider the empty language. All prefixes have the same empty residual, so its minimal complete DFA has exactly one nonaccepting state, with a loop on every letter. The language containing every word also has one state, but that state is accepting. Neither machine has zero states: a DFA must have an initial state, including when the alphabet has no usable transitions in a particular input word. This small example checks the treatment of the initial state and the empty continuation at the same time.
Summary
Residual languages identify exactly the information about a prefix that can affect future acceptance. Their number is the state complexity of a regular language. Refinement computes the same equivalence relation on a finite machine, and a distinguishing suffix is a certificate that a proposed merger is wrong.
The figure uses a separate five-state binary machine, not the unary examples above. Compare its reachable-state refinement with those examples.
Exercises
Quick check
(Find the minimal complete DFA for binary words ending in , including the empty word's status.)
Ask what a state must remember about the last symbol read.
Solution · Answer
Use states for whether the last symbol is ; is initial and rejects, accepts. A sends either state to and a sends either to . They are distinguished by , proving minimality.
Quick check
(Give a distinguishing suffix for and when in .)
Choose the suffix that completes the block of s exactly for the shorter prefix.
Solution · Answer
Choose . Then , while because . This includes , where the suffix is .
Quick check
(Explain why a reachable state that accepts no continuation can be merged with any other reachable state with the same property.)
Compare the residual languages of the two states.
Solution · Answer
Both states have the empty residual language, so they are equivalent. The quotient construction preserves all continuations; reachability does not prevent a safe merger.
Quick check
(For unary words, show that the language of lengths divisible by needs at least three states.)
Look at the prefixes , , .
Solution · Answer
The residual after is . For , choose with ; then is accepted after but not after . So the three prefixes have pairwise different residuals, giving the lower bound; a cycle of three states attains it.