The "a^n b^n" language isn't a regular language; this can be easily proved with the pumping lemma.

Suppose the language were regular. Since it's infinite, for large enough n the pumping lemma guarantees the decomposition a^n b^n = x y z, with nonempty y, such that x y^k z is always in the language.

This is clearly absurd: either y consists wholly of a's, and then x y^2 z contains more a's than b's, or it consists wholly of b's, and then that word contains more b's than a's, or else it contains a's and then b's - but then x y^2 z is of the form a^n_1 b^n_2 a^n_3 b^n_4, which clearly is not in the language.

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