JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

The Myhill-Nerode Theorem

The pumping lemma can only ever say 'not regular', and even then only sometimes. This guide hands you a sharper instrument that decides the question both ways: a language is regular exactly when its strings fall into finitely many genuinely different futures.

Why we need a sharper tool

By now you can wield the pumping lemma to prove a language non-regular, and you have met the painful catch: it is necessary but not sufficient. Passing the pumping test proves nothing — there exist non-regular languages that the pumping lemma cannot catch, so a clean 'it pumps' verdict leaves you exactly where you started. We have a tool that sometimes says 'no' and never honestly says 'yes'. That asymmetry is uncomfortable. What we really want is a single criterion that decides regularity in both directions.

The Myhill-Nerode theorem is exactly that criterion. Instead of poking at one machine and one pumped substring, it steps back and asks a question about the language itself: how many genuinely different situations can a reader be in after consuming some prefix of the input? If the answer is a finite number, the language is regular. If the answer is infinite, it is not. No machine required to ask the question, and the answer is an if-and-only-if.

The key idea: when do two prefixes share a future?

Picture a turnstile that has read some prefix and now waits for the rest of the input. The only thing that matters about its past is this: which continuations would eventually lead to acceptance? Two prefixes x and y are called indistinguishable with respect to a language L if, for every possible continuation string z, the verdict is the same — that is, 'xz is in L' agrees with 'yz is in L' for all z. This is the relation of string indistinguishability. If even one continuation z separates them (xz accepted but yz rejected, or vice versa), then x and y are distinguishable, and z is a witness that tells them apart.

Indistinguishability is an equivalence relation on all of Sigma-star (the set of all strings over the alphabet), so it carves every string into equivalence classes: each class is a bundle of prefixes that share exactly one future. It also has a tidy property called being right-invariant (this is the right-invariant relation idea): if x and y are indistinguishable, then sticking the same symbol on the end of both — xa and ya — keeps them indistinguishable. That is precisely what lets a finite machine append symbols one at a time without ever needing to remember which exact prefix it read, only which class it is in.

Counting the futures: the index of a language

Now count those equivalence classes. The number of indistinguishability classes is called the index of the language (the index of a language). The Myhill-Nerode theorem states it as a clean equivalence: a language L is a regular language if and only if its index is finite. A finite number of distinct futures means a finite number of states a machine could ever need; an infinite number of distinct futures means no finite memory could keep them apart. Better still, the theorem is quantitative — the index equals the exact number of states in the smallest possible DFA for L.

Let's see it cut both ways on a tiny example: L = strings over {a, b} with an even number of a-s, a language you designed a DFA for back in the DFA rung. How many futures are there? After reading any prefix, the only thing that can change the verdict is whether you have seen an even or an odd count of a-s so far. Two prefixes with the same parity are indistinguishable (any continuation flips both the same way); two with different parity are distinguished by, say, z = epsilon if the language asks for even, or by appending one 'a'. So there are exactly two classes — even and odd — the index is 2, and indeed the minimal DFA has 2 states.

Now run it on the classic villain L = a^n b^n (equal numbers of a-s then b-s), the language from proving non-regularity earlier in this rung. Consider the prefixes a, aa, aaa, ..., a^i, .... Are any two of them indistinguishable? Take a^i and a^j with i not equal to j. Append the continuation z = b^i. Then a^i b^i is in L, but a^j b^i is not (the counts disagree). So every distinct power of a sits in its own class — infinitely many classes, infinite index, not regular. Notice this is an honest 'yes/no' verdict the pumping lemma could only deliver one half of.

Why finitely many classes give you a machine

The 'only if' direction (regular implies finite index) is quick: a DFA with k states sorts every prefix into one of k buckets by where it lands, and prefixes landing on the same state must be indistinguishable, because from then on the machine behaves identically. So the index can be at most k — finite. The 'if' direction is the magic: from a finite set of classes you can build a machine, with no DFA given in advance. This construction is the heart of the theorem, so let us walk it.

  1. Make one state for each indistinguishability class. Because the index is finite, this is a finite set of states — call the class of a prefix x the box [x].
  2. The start state is the class of the empty string, [epsilon] — the situation before any symbol has been read.
  3. Define the transition by appending a symbol: delta([x], a) = [xa]. Right-invariance is exactly what makes this well-defined — if you had picked a different representative y from the same class, [ya] would be the same box, so the move does not depend on which prefix you happened to name.
  4. Mark a class as accepting exactly when its strings are in L. By the z = epsilon remark, every string in one class agrees on membership, so 'is this class accepting?' is a consistent question.
  5. Feed any input into this machine and it walks class to class; it ends in an accepting class exactly when the whole input is in L. So the machine recognizes L — and it has exactly index-many states.

There is a satisfying pigeonhole flavour here, the same pigeonhole principle that powered the pumping lemma. Finite states means finitely many pigeonholes; if a language genuinely needs to tell apart infinitely many situations, some two truly-different prefixes are forced to share a hole, and then a continuation that should split them cannot — contradiction. Myhill-Nerode just makes the pigeonholes precise: they are the equivalence classes, neither more nor fewer.

The minimal machine falls out for free

The machine built in the previous section is not just a DFA for L — it is the smallest one. Any DFA for L needs at least one state per class (its states cannot be fewer than the futures it must keep apart), and the Myhill-Nerode machine uses exactly one per class, so nothing can beat it. Even better, this minimal machine is unique up to renaming the states — every DFA that achieves the minimum is essentially the same diagram with different labels. That uniqueness is what makes 'the minimal DFA' a meaningful phrase rather than 'a minimal DFA'.

This is the doorway to the next and final guide of the rung. In practice you rarely start from the abstract classes; you usually already hold some DFA — perhaps a bloated one spat out by the subset construction — and you want to shrink it. DFA minimization does this by the mirror image of Myhill-Nerode: it merges states that turn out to be indistinguishable from each other, repeatedly, until only genuinely different states remain. What survives is precisely the class structure the theorem describes — the Myhill-Nerode theorem proves the destination exists and is unique; minimization is the algorithm that walks you there.