Why is {a^nb^n | n >= 0} not regular?

What you’re looking for is Pumping lemma for regular languages.

Here is an example with your exact problem:

Examples:
Let L = {ambm | m ≥ 1}.
Then L is not regular.
Proof: Let n be as in Pumping Lemma.
Let w = anbn.
Let w = xyz be as in Pumping Lemma.
Thus, xy2z ∈ L, however, xy2z contains more a’s than b’s.

Leave a Comment