The Myhill–Nerode Theorem

Symptom

You need to prove a language is not regular. Everyone points you at the pumping lemma, and you spend an afternoon losing to it.

The statement is a nest of quantifiers: for every regular language there exists a pumping length $p$ such that for every string $w$ with $|w| \ge p$ there exists a decomposition $w = xyz$ with $|xy| \le p$ and $|y| > 0$ such that for all $i \ge 0$, $xy^i z$ is in the language. To use it you negate all of that and play a game against an adversary who picks $p$ and the decomposition while you pick $w$ and $i$.

When it works, it works. But it fails in two ways that waste real time. First, picking the wrong $w$ leaves you stuck with no indication that the string was the problem. Second, and worse, the pumping lemma is not an iff. There are non-regular languages that pump. So a failed attempt tells you nothing at all, and you cannot use it to prove a language is regular.

Meanwhile a different question is nagging: your regex library minimized a DFA from 40 states to 12, and you want to know whether 12 is really the floor or whether a smarter algorithm finds 11.

Both questions have the same answer, and it is not the pumping lemma.

Statement

For a language $L$ over $\Sigma$, define strings $x$ and $y$ to be equivalent when no suffix distinguishes them:

$$x \equiv_L y \iff \forall z \in \Sigma^* : (xz \in L \iff yz \in L).$$

This is the Nerode right congruence. Two prefixes are equivalent when the future cannot tell them apart.

$L$ is regular if and only if $\equiv_L$ has finitely many equivalence classes. Moreover, the number of classes is exactly the number of states in the unique minimal DFA for $L$.

Three results in one. A characterization (iff, unlike the pumping lemma), an exact state count, and a uniqueness claim — the minimal DFA is not one minimal DFA among several but the minimal DFA, canonical up to renaming.

Argument

Regular implies finite index. Let $M$ be a DFA for $L$ with states $Q$. If $\delta(q_0, x) = \delta(q_0, y)$, then $x$ and $y$ drive the machine to the same state, and everything afterwards is identical, so $xz$ and $yz$ are accepted together. Hence $x \equiv_L y$. So the map from states to classes is onto, and the index is at most $|Q|$, which is finite.

Notice this already proves the lower bound: any DFA for $L$ has at least as many states as $\equiv_L$ has classes.

Finite index implies regular. Build a DFA whose states are the classes. Start state $[\varepsilon]$; transition $\delta([x], a) = [xa]$; accept $[x]$ when $x \in L$.

Both need checking. The transition is well-defined: if $x \equiv_L y$ then $xa \equiv_L ya$, since any $z$ distinguishing $xa$ from $ya$ means $az$ distinguishes $x$ from $y$. The accept set is well-defined: taking $z = \varepsilon$ in the definition shows equivalent strings agree on membership. Finite index makes it a finite automaton, and by construction it accepts exactly $L$.

Uniqueness. Any DFA for $L$ with the minimum number of states must have its states in bijection with the classes, and the transitions are then forced by the construction. So minimal DFAs are isomorphic. Contrast minimal NFAs, which are neither unique nor efficiently computable — NFA minimization is PSPACE-complete. Determinism is what buys canonicity.

Using it: $L = {a^n b^n}$. Consider $a^i$ and $a^j$ for $i \ne j$. The suffix $b^i$ distinguishes them: $a^i b^i \in L$ but $a^j b^i \notin L$. So every $a^i$ is in its own class, giving infinitely many, so $L$ is not regular.

That is the whole proof. No quantifier alternation, no adversary, no choosing a clever $w$. Exhibit an infinite family of pairwise distinguishable prefixes and you are done, and the family is usually the obvious one.

Why it subsumes the pumping lemma. The pumping lemma is a consequence of finite index: with $k$ states, any string of length $\ge k$ revisits a state, and the loop is the pumpable part. But it is a one-way consequence, which is why it cannot certify regularity. Myhill-Nerode is the underlying fact, and it goes both ways. Anything the pumping lemma proves, Myhill-Nerode proves, usually in fewer lines. The reverse fails — ${a^i b^j c^k : i = 1 \implies j = k}$ pumps but is not regular, and Myhill-Nerode disposes of it directly.

Where minimization algorithms come from. Hopcroft’s $O(n \log n)$ algorithm computes $\equiv_L$ by partition refinement: start by splitting accepting from non-accepting states, then repeatedly split any block whose members transition into different blocks. It terminates at the Nerode classes, and the theorem is why the answer is canonical rather than dependent on the order of refinement.

A worked count, since the theorem gives an exact number and that is unusual. Take $L$ = binary strings whose value is divisible by 3, read most significant bit first. How many states does the minimal DFA have?

Do not build an automaton. Just count Nerode classes. Reading a prefix $x$, the only thing the future needs to know is the value of $x$ modulo 3, because appending a bit $b$ maps value $v$ to $2v + b$, and that map depends on $v$ only through $v \bmod 3$. So there are at most three classes, and they are genuinely distinct: $\varepsilon$ (value 0), 1 (value 1), and 10 (value 2) are pairwise distinguishable, since appending 0 accepts exactly the first. Exactly three states, proved without drawing anything, and a brute-force count of the classes over all prefixes up to length 14 confirms it.

Now change the language slightly: binary strings divisible by 3 whose length is even. The future needs the residue and the parity of the length, and all six combinations are reachable and distinguishable, so the minimal DFA has exactly six states. The product structure appears in the count directly.

Contrast $L = {a^n b^n}$ from above, where the classes $[a^0], [a^1], [a^2], \dots$ are pairwise distinguishable and there are infinitely many. The same counting procedure answers both “how many states” and “is it regular at all,” which is what makes this the tool to reach for first. You are always doing the same thing: asking what the minimum is that a prefix must tell you about itself, and then checking whether the answer fits in a bounded amount of memory.

Forbids

A DFA for ${a^n b^n}$, palindromes, balanced parentheses, or ${ww}$, all by the same one-line argument.

A DFA smaller than the Nerode index. This is a hard floor. No optimization, no state encoding, no clever alphabet trick goes below it.

Multiple structurally different minimal DFAs. They are all the same machine with relabelled states, which is what makes DFA equality decidable: minimize both and check isomorphism.

Finite automata for anything requiring unbounded memory of the input. If distinguishing prefixes requires remembering an unbounded quantity, the index is infinite. This is the honest formulation of “regular languages cannot count,” and it is the mechanism behind T038’s ladder.

Does not forbid

It does not forbid small NFAs for languages with huge DFAs, which is the point people miss when they conclude a language is “expensive.” The language “the $k$-th symbol from the end is $a$” has exactly $2^k$ Nerode classes — a million-plus states at $k = 20$ — because you must remember the last $k$ symbols. But an NFA does it with $k+1$ states by guessing. The theorem bounds DFAs only, and this gap is why RE2 and Rust’s regex simulate NFAs with lazy DFA caching rather than building the DFA up front (T039).

It does not make minimization expensive. Hopcroft’s algorithm is $O(n \log n)$ and is what flex, ANTLR’s lexer generator, and hardware synthesis tools run routinely on generated automata. The theorem says a canonical answer exists; the algorithm finds it quickly.

It does not mean non-regular languages are impractical. Balanced parentheses are not regular and every parser handles them. You move up the hierarchy to a pushdown automaton and get a stack. Non-regular means “needs more than finite memory,” not “hard.”

It does not apply to the extended regexes in your language’s standard library. Backreferences are not regular, so a re pattern using them has no DFA and no Nerode index, and reasoning about it with this theorem is a category error.

It does not mean the minimal DFA is the best implementation. Minimal state count is not minimal memory — a 12-state DFA over a 256-symbol alphabet has a 3072-entry transition table, and a larger automaton with a compressible structure may be faster in cache. Real lexers use table compression, and sometimes a non-minimal automaton wins. The theorem answers “how few states” and that is a different question from “how fast.”

Boundary

The theorem is specifically about DFAs over finite alphabets, and its relatives mark the edges:

• NFAs: no unique minimum, and minimization is PSPACE-complete.
• Context-free languages: no analogue. There is no canonical minimal pushdown automaton, and equivalence of CFGs is undecidable — which is exactly why grammar conflicts in a parser generator are reported rather than resolved.
• Weighted and probabilistic automata: analogues exist via the Hankel matrix, where rank plays the role of index. This is the basis of spectral learning for hidden Markov models.
• Infinite alphabets: register automata and nominal automata, where the theory partially survives.

The idea to keep is the reframing. A DFA state is not a place; it is an equivalence class of histories, the answer to “what is the minimum I must remember about the past to behave correctly in the future?” That question makes sense far beyond automata — it is what a state machine in your codebase should be storing, and it is a good test to run on one. If two of your states never lead to different behaviour, they are the same state, and Myhill-Nerode says so.

Read next