Myhill Theorem proof that the "a^n b^n" language is not regular (idea) by ariels

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.

pumping lemma proof that the "a^n b^n" language is not regular	"a^n b^n" language	Myhill Theorem proof that the balanced braces language is not regular	Myhill / Nerode Theorem
regular language	Proof of the Myhill Theorem	pumping lemma	K's Choice
factor theorem	Frobenius-Konig theorem	Red Meat Construction Set	Nash equilibrium
Connecting the NES Control Deck to your TV set	type	suffix	Gödel's theorem
proof	recursive