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.

# Proof of the Myhill Theorem (idea)

See all of Proof of the Myhill Theorem, there is 1 more in this node.