Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

In a CS course I'm taking there is an example of a language that is not regular:

{a^nb^n | n >= 0}

I can understand that it is not regular since no Finite State Automaton/Machine can be written that validates and accepts this input since it lacks a memory component. (Please correct me if I'm wrong)

The wikipedia entry on Regular Language also lists this example, but does not provide a (mathematical) proof why it is not regular.

Can anyone enlighten me on this and provide proof for this, or point me too a good resource?

like image 492
Christophe Herreman Avatar asked Feb 22 '10 08:02

Christophe Herreman


1 Answers

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.

like image 183
cletus Avatar answered Sep 29 '22 02:09

cletus