For comparison with the pumping lemma proof that the "a^n b^n" language is not regular, I give a proof using the Myhill theorem.

To prove the "a^n b^n" language is not a regular language using this theorem, we must demonstrate an infinite number of prefixes with incompatible suffix sets S(x). But these are trivially available: if we take x_n=a^n, then S(x_n) contains the word b^n; this suffix is not in S(x_m) for any other m. So we have an infinite number of types for S(x), thus the language is not regular.

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