Myhill-Nerode Theorem & DFA Minimization

Equivalence classes count states and pin down the minimal DFA.

The idea

The Myhill-Nerode theorem characterizes the regular languages by an equivalence relation on strings. For a language $L$, call two strings $x$ and $y$ equivalent, written $x \equiv_L y$, when no suffix tells them apart: for every string $z$, $xz \in L$ exactly when $yz \in L$.

Theorem (Myhill-Nerode theorem).

A language $L$ is regular if and only if $\equiv_L$ has finitely many equivalence classes, and in that case the number of classes equals the number of states of the smallest DFA recognizing $L$.

The theorem counts the memory a DFA needs. After the machine reads a prefix $x$, the only thing about $x$ that can still matter is which suffixes $z$ would complete it into a member of $L$, and $\equiv_L$ groups together exactly the prefixes for which that information is the same.

To show $x$ and $y$ lie in different classes, exhibit one suffix that separates them. An infinite family of pairwise separated strings shows $\equiv_L$ has infinitely many classes, so $L$ is not regular. Unlike a pumping argument, this is a characterization rather than a one-way test: the theorem can certify regularity as well as refute it.

Ways to work on it

• Walkthrough. Learn how distinguishing strings partition a language and decide its regularity.
• Practice. Count the Myhill-Nerode classes, i.e. the minimal-DFA states.
• Hardest. Minimize a given DFA to its smallest equivalent automaton.

Not sure where to start? Take the ten-question placement test.