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

Question

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?

Cardin

Answer 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.

Gimcrackery

last claim needs better explanations. The x2yz word would either contain more letters of one sort (if y has more a's than b's or vice versa), or duplicating it would shatter the letter order, in which b's should come after all a's. – Houseyhousey

incomplete proof. you haven't defined x,y,z. x has only the limitation that | xy | <= p, where p is the pumping length. you have to split your proof in three cases, with y strings based on (a|ab|b) for it to be complete. xy could well consist of more b than a's: x=a, y=b^n, z=b – Arrogate

The proof misses some parts, as such it is incorrect. Plus the link is broken. – Derrick

Answer 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.

Insignificance

Answer 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.

Ufo

Answer 4

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.

Baronial

Answer 5

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'.

Kneepad

Answer 6

Let me explain here with an example :

L = {a^n.b^n | n >= 0};

minimum length string accepted in L is :

{ε, ab, aabb, ...} => minimum w = ab;

I did not took n == 0, since for n == 0, y can never be |y| > 0.

let's first take x = ε, then y = a and z = b or y = ab and z = ε, since |y| > 0 and |xy| <= 2 (since its an infinite language, p(here 2) can be as max as length of string reference here)

after pumping y = a :

L' = aab, aaab, aaaab, aaaaab;

after pumping y = ab:

L' = abab, ababab, abababab;

Now, take x = a, then y = b and z = ε; after pumping y = b :

L' = abb, abbb, abbbb, abbbbb;

Again check for w = aabb : w is in L;

for x can be ε, a, aa, aab, then y can be a, aa, bb, ab, aab, ... aabb and z can be ε, b, bb, abb;

In all the above case L' generated after pumping any length of y will not be accepted in L. L' either has unequal a, b or the order is not as per definition. Hence, the L = {a^n.b^n | n >= 0}; is not regular since it fails Pumping lemma for regular languages.

Oglethorpe

Answer 7

Pumping lemma can be used to disprove a language is not regular,

Example:

Let L = {a^mb^m | m ≥ 1}

Then L is not regular.

Proof: Assume L is regular.

Let n be as in Pumping Lemma.

Let w = a^nb^n.

Let w = xyz be as in Pumping Lemma.

Now y contains only 'a' since |xy|<= n and i = 2 ( in xy^iz ).

Thus, xy^2z ∈ L, however, xy^2z contains more a’s than b’s.

Which is a contradiction to the first assumption, so its not regular.

Jaye