The Myhill Nerode Theorem, and a Second Way to Prove a Language Not Regular

The first half: a regular language has finite index

Suppose L is regular, so some DFA M with n states accepts it.

If delta hat(q0, x) equals delta hat(q0, y), then x and y are L-equivalent. The reason is the identity of chapter 11: delta hat(q0, xz) equals delta hat from the state reached after x on z, and the same for y, so if those states are the same then both end in the same state on every z, and so agree about acceptance.

So the map sending a string x to the state delta hat(q0, x) is constant on L-equivalence classes, and therefore there are at most as many classes as there are states. At most n classes: finite.

The second half: finite index gives a machine

Suppose the relation has finitely many classes. Build a machine whose states are the classes.

States: the L-equivalence classes. Start state: the class of the empty string. Transition: from the class of x on symbol a, go to the class of xa. This is well defined and it is the only thing that needs checking: if x and y are L-equivalent, then xa and ya are L-equivalent, because any z distinguishing xa from ya would make az a distinguishing extension of x and y. Final states: the classes whose members are in L. Well defined because the empty string is a legal z, so two L-equivalent strings are both in L or both out.

Then, by induction on the length of w, the machine reaches the class of w on input w, so it accepts w exactly when the class of w is final, which is exactly when w is in L. So L is regular, and the machine has one state per class.

Putting the halves together gives the theorem, and one more thing: the machine just built has exactly index-many states, and the first half showed no machine can have fewer. So it is minimal, and it was constructed from the language alone with no reference to any machine. That is the uniqueness chapter 20 promised: any minimal DFA for L must have index-many states, and merging its states by the relation gives this same machine, so all minimal DFAs for L are the same up to the names of their states.

Worked example 1: a regular language, and its index

Let L be the strings over {a, b} that end in ab. Chapter 13's machine has three states, so the index should be 3, and here are the three classes with the reasoning.

The only thing that matters about a string, for deciding whether anything appended to it ends in ab, is how much of ab it currently ends with. So the candidate classes are:

Three, and no more: every string falls into one of the three, because it either ends in ab, or ends in a without ending in ab, or neither.

Three, and no fewer: each pair is distinguished by an explicit z, which is what a proof requires.

So the index is exactly 3, the language is regular, and the minimal DFA has 3 states. Here it is, being the machine of chapter 13 with its states renamed after the classes:

Accepts: ab, aab, bab, abab

Rejects: ε, a, b, ba, aba, abb

The claim is checked, so the machine really does have the smallest possible number of states, which the index argument predicted.

Worked example 2: a language proved NOT regular

Let L be the set of strings a to the n followed by b to the n, for n at least 0. So L holds epsilon, ab, aabb, aaabbb and so on.

Claim. L is not regular.

Proof by Myhill Nerode. Consider the infinitely many strings

that is, a to the i for every i at least 0. Take any two of them with different exponents, say a to the i and a to the j with i less than j. Then the extension

distinguishes them: a to the i followed by b to the i is in L, while a to the j followed by b to the i is not, because j is not i.

So no two of these strings are L-equivalent, and there are infinitely many of them, so there are infinitely many classes. The index is infinite, and by the theorem L is not regular.

That is the whole proof. Compare it with the pumping lemma proof of the same fact in chapter 37, which needs a supposed machine, a pigeonhole argument and a case analysis. This one needs an infinite family and one distinguishing extension.

The shape to remember, because every such proof has it:

1. Name an infinite family of strings, indexed by a number.
2. Take any two of them with different indices.
3. Produce one z, written in terms of the indices, that is accepted after one and not after the other.
4. Conclude that there are infinitely many classes, so the language is not regular.

Step 3 is the whole work, and step 1 is where the thinking goes: the family has to be chosen so that a distinguishing extension exists.

Worked example 3: a second language, for the pattern

Let L be the set of palindromes over {a, b}, that is, strings equal to their own reversal.

Family: a to the i followed by b, for i at least 1. So ab, aab, aaab, and so on.

Take two, with i less than j. Distinguishing extension: z equal to a to the i. Then a to the i, then b, then a to the i is a palindrome, because it reads the same both ways. But a to the j, then b, then a to the i is not, because it has j of a at the front and i at the back and j is not i.

Infinitely many classes, so the palindromes are not regular. Chapter 56 builds a pushdown automaton for this language, which is the machine that can do it.

Worked example 4: a language that IS regular, proved so

The theorem works in this direction too, which the pumping lemma cannot do.

Let L be the strings over {0, 1} whose value as a binary number is divisible by 3, as in chapter 13's machine 4.

Claim. The index is at most 3, so L is regular.

Proof. If x and y have the same remainder on division by 3 when read as binary numbers, then for any z the numbers xz and yz have the same remainder as each other, because appending a bit b takes a number n to 2n plus b, and that operation depends only on n's remainder. So xz is in L exactly when yz is, and x and y are L-equivalent. There are only three remainders, so there are at most three classes, and the index is finite. By the theorem, L is regular.

And it is exactly 3, because 0, 1 and 10 have remainders 0, 1 and 2 and so lie in three different classes, each pair being distinguished: 0 and 1 by the empty extension, 1 and 10 by the extension 1, since 11 is 3 and is divisible by 3 while 101 is 5 and is not.

Distinctions

What it does NOT mean

It is not about equal strings. Two L-equivalent strings can look nothing alike: aab and bbbab are in the same class for the ends-in-ab language.

Finite index is not the same as a finite language. The ends-in-ab language is infinite and has index 3.

The classes are not the language and its complement. They are classes of Sigma star under the relation, and there are as many as the minimal machine has states, some of them classes of strings not in L at all.

Producing one distinguishing extension is not enough on its own. You need infinitely many pairwise distinguishable strings. One pair proves two classes, which proves nothing.

The theorem does not give an algorithm for the index of an arbitrary language. It characterises regularity; identifying the classes still takes an argument.

Quick revision

• x and y are L-equivalent when, for every z, xz is in L exactly when yz is. Such a z that separates them

is a distinguishing extension.

• It is an equivalence relation on Sigma star, and the number of classes is its index.
• Myhill Nerode: L is regular if and only if the index is finite, and then the index is the number of states

of the minimal DFA.

• Half one: strings reaching the same state are L-equivalent, so classes are at most states.
• Half two: build a machine whose states are the classes, start at the class of epsilon, move from the class

of x on a to the class of xa, and make final the classes inside L.

• Hence the minimal DFA is unique up to state names, which is what chapter 20 relied on.
• To prove a language not regular: name an infinite family, and for any two members give one z that

separates them.

• Unlike the pumping lemma it is an if and only if, so it can also prove a language regular.

Test yourself

1. Define the Myhill Nerode relation, and say what a distinguishing extension is. x is L-equivalent to y when for every string z, xz is in L exactly when yz is in L. A distinguishing extension is a z for which the two disagree, which proves the strings are in different classes.

2. State the theorem, both halves, and the extra fact about counting. L is regular if and only if the relation has finitely many classes, and when it does, the number of classes equals the number of states of the minimal DFA for L.

3. Prove that the language of strings over {a, b} with equally many a and b is not regular. Take the family a to the i for i at least 0. For i less than j, the extension b to the i is accepted after a to the i and not after a to the j, since the second has j of a and i of b. So there are infinitely many classes and the language is not regular.

4. The ends-in-ab language has index 3. Name the three classes and one extension separating each pair. The class of strings ending in neither a nor ab, of strings ending in a but not ab, and of strings ending in ab. The extension b separates the first from the second; the empty string separates the first from the third and the second from the third.

5. Why can the pumping lemma not prove a language regular, while this theorem can? Because the pumping lemma is a one way implication: regular languages pump, so failing to pump proves irregularity, but pumping successfully proves nothing. Myhill Nerode is an equivalence, so finite index proves regularity outright.

6. A student gives one pair of distinguishable strings and concludes the language is not regular. What is missing? Infinitely many pairwise distinguishable strings. One pair shows only that the index is at least 2, which every non trivial language satisfies.