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?

Solution 1:

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

Here is an example with your exact problem:

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

Solution 2:

Because you can't write a finite state machine that will 'count' identical sequences of 'a' and 'b' symbols. In a nutshell, FSMs cannot 'count'. Try imagining such a FSM: how many states would you give to symbol 'a'? How many to 'b'? What if your input sequence has more?

Note that if you had n <= X with X an integer value you could prepare such FSM (by having one with a lots of states, but still a finite number); such language would be regular.

Solution 3:

The reason is, you have to reach the final state only when no. of 'a' and no. of 'b' are equal in the input string. And to do that you have to count both, the no. of 'a' as well as no. of 'b' but because value of 'n' can reach infinity, it's not possible to count up to infinity using a Finite automata.

So that's why {a^n b^n | n >= 0} is not regular.

Solution 4:

Finite State Automaton has no data structure (stack) - memory as in case of push down automaton. Yeah it can give you some 'a's followed by some 'b's but not exact amount of 'a' followed by that no 'b'.

Solution 5:

Assume L = {aⁿbⁿ | n ≥ 0} is regular. Then we can use the pumping lemma.

Let n be the pumping lemma number. Consider w = aⁿbⁿ∈L. The pumping lemma states that you can divide w into xyz such that xy ≤ n, y ≥ 1 and ∀ i∈ℕ₀: xyⁱz∈L.

Using the first two rules we can easily see that no matter how we divide w into xyz, y will always consist of only as and that it will contain at least one such letter. With rule 3 we conclude that a^n-kbⁿ∈L where k = |y| ≥ 1. But n-k ≠ n violates the definition of L, so that a^n-kbⁿ∉L. This is a contradiction 🗲 and we conclude that the assumption that L is regular is false.