display | more...

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.

Consider a set of strings, call it L for the moment. The set may be infinite. Consider the set of prefixes of L, that is, strings that can be completed to strings in L. For each prefix w, consider its set of completions SL(w), that is, the set of strings that complete w to a string in L.

The theorem says: L is regular iff its number of different completion sets is finite.

Log in or register to write something here or to contact authors.