Distinguishing Strings and the Myhill-Nerode Theorem

Every deterministic automaton induces an equivalence relation on strings: two strings are related when they leave the machine in the same state. The Myhill-Nerode theorem says the converse also holds, and that the relation can be defined without reference to any machine at all. That independence is what makes it a tool: it converts a question about automata into a question about the language, and it supplies the lower bounds that the subset construction’s exponential needs in order to be called tight.

The relation, defined on strings

For a language L ⊆ Σ*, define x ≡_L y to hold when for every z ∈ Σ*,

xz ∈ L if and only if yz ∈ L.

The string z is the distinguishing continuation, and x, y are indistinguishable when no continuation separates them. The relation is an equivalence relation for the trivial reason that the condition is a statement about membership, which is symmetric in x and y and transitive through shared behaviour.

Each equivalence class is characterized by the set of continuations that lead into L. Call that set the right context of the class. Two strings are in the same class exactly when their right contexts are equal. The number of classes is the index of the relation, and it is either finite or infinite.

The relation is a right congruence: if x ≡_L y, then xa ≡_L ya for every symbol a. This follows by substituting az for z in the definition. The congruence property is what allows the classes to serve as states: appending a symbol must map a class to a well-defined class, independent of which representative was chosen.

The theorem in three directions

The theorem asserts that these are equivalent for any language L:

1. L is accepted by some DFA.
2. L is the union of some of the equivalence classes of a right congruence of finite index.
3. The relation ≡_L has finite index.

And when they hold, the number of states in the minimal DFA for L equals the index of ≡_L.

The first direction constructs the machine: take the classes as states, the class of the empty string as the start, and the classes whose right context contains the empty string as accepting. Since ε ∈ L exactly when x ∈ L for any x in the class (substitute z = ε), the accepting classes are precisely those containing a string of L. The transition on a sends the class of x to the class of xa, which is well defined by the congruence property.

The second direction is the observation that any DFA’s state relation is a right congruence of finite index that refines ≡_L, so a machine with n states induces at most n classes.

The third direction is the lower bound: if ≡_L has index k, no DFA with fewer than k states can accept L, because two strings in different classes must lead to different states, and a machine with fewer states would have to put them in the same one.

Using the theorem to prove non-regularity

The pump lemma is the usual tool for showing a language is not regular, and it is a corollary of this theorem. The theorem gives a cleaner argument when the language has an obvious infinite family of pairwise distinguishable strings.

For L = { a^n b^n : n ≥ 0 }, consider the strings a^i for i ≥ 0. For i ≠ j, take z = b^i. Then a^i b^i ∈ L but a^j b^i ∉ L, so a^i and a^j are distinguishable. There are infinitely many such strings, pairwise distinguishable, so the index is infinite and no DFA accepts L. The argument is one line longer than the pump lemma proof and does not require choosing a pumping length.

The same style gives the exponential lower bound for the “k-th symbol from the end” language. Two k-bit strings u and v that differ in some position are distinguished by a continuation of length k that places the differing bit in the critical position; strings that agree on all k bits are indistinguishable. The classes are exactly the 2^k bit patterns, so the minimal machine has 2^k states. This is the bound that the subset construction attains, and the theorem is what proves no better construction exists.

Reading the classes off a machine

Given a DFA, computing ≡_L is the same as minimizing it: partition refinement produces the classes of the state relation, and the state relation coincides with ≡_L when the machine is minimal and has no unreachable states. The correspondence is exact enough that partition refinement can be described as an algorithm for computing the index of ≡_L without enumerating strings.

There is a subtlety about unreachable states. A DFA may have states that no input reaches; those states induce classes that do not correspond to any string’s right context, because no string leads there. The state relation of such a machine refines ≡_L strictly. Removing unreachable states first makes the relations coincide.

A second subtlety is that the state relation depends on the machine, while ≡_L depends only on the language. Two different minimal machines for the same language have isomorphic state relations, so the classes are the same up to renaming. That is the content of the uniqueness claim.

The syntactic monoid, briefly

The right congruence is the first level of a richer structure. Define x ≈_L y when for all u, v ∈ Σ*, uxv ∈ L iff uyv ∈ L. This is a two-sided congruence, finer than ≡_L, and its classes form a finite monoid under concatenation when L is regular. The monoid is called the syntactic monoid of L, and its size can exceed the number of DFA states, sometimes exponentially.

The monoid matters because it is invariant under the choice of machine and because algebraic properties of the monoid correspond to properties of the language that no DFA state count reveals. A language is piecewise testable exactly when its syntactic monoid is aperiodic and J-trivial; that characterization, due to Simon, is not expressible as a condition on the minimal DFA’s shape. The same algebraic route underlies the dot-depth and star-height hierarchies.

For an automaton practitioner the monoid is mostly a source of lower bounds and a reminder that the minimal DFA is not the finest invariant available. Two languages with the same minimal DFA state count can have syntactic monoids of very different sizes, so state count alone does not classify them.

What the theorem does not give

The theorem is an existence statement. It says a minimal machine exists and its size is the index, but it gives no procedure for computing the index other than building a machine or running refinement. For a language given by a regular expression, the practical route is still construction followed by minimization, and the theorem’s role is to certify that the result cannot be improved.

It also says nothing about the time needed to find the minimal machine. The index is a number; computing it from a description of the language can be expensive, and the problem of minimizing a DFA given as a table is known to be solvable in O(n log n) but not known to be solvable in linear time for the general case with a large alphabet.

Finally, the theorem applies to languages over a finite alphabet, and the finiteness of the alphabet is used when the congruence is shown to be determined by finitely many symbols. Languages over infinite alphabets, such as strings of integers, do not have finite-index right congruences in the same sense, and the theory of register automata exists precisely to handle that case with a different equivalence notion.

The practical value is narrower and more reliable: given a candidate machine, the theorem says the only way to shrink it is to find two states that no continuation distinguishes, and given a language, the theorem says the only way to bound a machine’s size from below is to exhibit pairwise distinguishable strings. Both are constructive, and both are used every time a lexer generator reports the size of the table it is about to emit.