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.