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 S

_{L}(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.