Asked By : doniyor
Answered By : Boris Trayvas
you guys are talking about unbounded memory which you mean is the reason why it is not regular. but a^nb^m can also have unbounded memory if i want, doesnot it? this is still giving me no peace.
The issue is not how big the words can get (you will usually encounter infinite regular languages, because every finite language is regular, and that’s pretty boring) but how much the DFA needs to remember.
In the $a^mb^n$ example, there is no need to remember $m,n$. The algorihm just needs to make sure they are positive and that the word is correctly ordered. This is a finite list, and each of the items on the list requires a constant amount of memory.
Compare this to $a^nb^n$, for which a simple alogrithm is required to remember that the number of $a$’s is equal to the number of $b$’s. This will require unbounded memory. When I look at a language and see that any algorithm I can think of needs unbounded memory, my intuition that the language is not regular grows stronger. If I can’t find a “smart” algorithm (one that requires a constant amount of memory) in a reasonable amount of time (how much time is reasonable is up to you) I will try proving the language is not regular.
Hope this makes it a bit clearer.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/2393