Proof of the Myhill Theorem

• 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.

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 S_L(w) brings it into an accepting state, if L is the language recognised by the dfa.