• Suppose L is a language on an alphabet Σ for which there are only a finite number of types for

      S(w) = {x: wx ∈ L}.
    We wish to show L is a regular language; we shall construct a finite state machine (a DFA) which recognises L. Let T be the (finite!) set {S(w) : w ∈ Σ*} (T is the set of types of S(w)). T shall be the set of our automaton's states.

    When in some state S(w), upon reading some letter a∈Σ of the alphabet, the automaton will switch to state S(wa). We must show this is well defined: if S=S(w)=S(u) for 2 words w, u, we must show S(wa)=S(ua). So suppose x is in S(w), and begins with a: x=ay. Then we know wx=way is in L, and thus y is in S(wa); all y's in S(wa) are of this form. But for such an x, x is in S(u)=S(w), so ux=uay is in L, and thus y is also in S(ua). Now switch u and w in the argument above, and conclude that S(ua)=S(wa). The set of accepting states of our automaton shall be F = {S(w): w is in L}, and the initial state shall be S() = S(ε) (ε is the empty word). It is straightforward (and left as an exercise for the reader) to verify that this does indeed define a DFA, which accepts L).

    Also note that we have shown that L is accepted by an automaton with |T| states.

  • Now suppose L is a regular language; we wish to show S(w) takes on finitely many types. Consider some DFA accepting L. For each of our automaton's k state s, define W(s) = {w : after reading w, the automaton is in state s}. Then if w,u are in W(s), we know S(w)=S(u) (if wx is in L, then we may read u, reaching state s, then read x and reach an accepting state; thus ux is also in L). So S(w) takes on at most k types -- a finite number.

    Also note that we have shown |T| ≤ k, so |T| is indeed the minimal number of states in a DFA accepting L.

(Creating this writeup was a mistake, but I can't nuke it so why not try to make the best of it.)

The basic observation is that completion sets (see the statement of the theorem for details) correspond to the states of a deterministic finite state automaton. Reading some string w brings the automaton into that state; subsequently reading a string in its completion set SL(w) brings it into an accepting state, if L is the language recognised by the dfa.

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