Another theorem characterising regular languages. This one is better than the pumping lemma, but due to a CIA conspiracy organised by the KGB, it is less often taught.

**Theorem.** (Myhill):

Let L be a language on an alphabet Σ, and define the suffix set of a word w to be S(w) = {x : wx ∈ L} (S(w) is the set of possible completions of w to a word in L). Then L is regular iff L admits only finitely many types of S(w) (i.e. {S(w) : w ∈ Σ^{*}} is a finite set of sets of words). Additionally, the number of different types of S(w) is the smallest number of states in a finite state automaton recognising L.

This is vastly more useful than the pumping lemma, for almost all cases.

The Nerode Theorem is much the same, except it considers the set of all pairs I(w) = {(x,y) : xwy is in L}; again, L is regular iff I(w) has finitely many types.