Consider a set of strings
, call it L for the moment. The set may be infinite
. Consider the set of prefix
es 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.