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?

computer-science fsm regular-language

Edit Report

1 Answer

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.

answered 2010-02-22T08:56:56.030

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

1 Answer

Your Answer