Myhill / Nerode Theorem (thing) by ariels

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.

pumping lemma	Proof of the Myhill Theorem	regular language	Myhill Theorem proof that the "a^n b^n" language is not regular
The set of decimal representations of numbers divisible by 17 is regular	Myhill Theorem proof that the balanced braces language is not regular	Lesch-Nyhan Syndrome	favicon.ico
finite state automaton	regex	Conspiracy	Lemma of Choice
Myhill-Nerode Theorem	the expressive power of regular expressions	pumping lemma proof that the balanced braces language is not regular	dangling else
Finite automaton	Regular	RDBMS	IFF
ether