# Finite Automata limitations

• Dec 5th 2010, 12:21 PM
tom9999
[SOLVED]Finite Automata limitations
I am trying to clear something that seems to be a little misleading for me.

I know the language over {a,b} consisting of all words containing the same number of occurrences of
the symbol a as of the symbol b is not regular.

I know that the language L over {a,b} consisting of all words containing
the same number of occurrences of ab as a substring as occurrences of ba as a substring
actually is regular.

What would be the best way to prove the sub string language??
by finding a finite automaton that accepts this language? or have i got the wrong idea?

Hope someone can point me in the right direction.
• Dec 6th 2010, 01:28 AM
emakarov
Yes, this seems surprising at first. The difference here is that recognizing the first language requires unlimited memory. Indeed, to check whether $a^nb^n$ is in the language, the automaton has to read all a's and remember their number, then read all b's and check that their number is the same as that of a's.

Recognizing the second language, on the other hand, does not require infinite memory because one cannot have a sequence of "ab" without also having "ba". Note that it is crucial that the alphabet does not contain other symbols besides a and b. Suppose there is a substring "ab". To have another "ab" further along, one must first encounter "ba". Therefore a counter that contains the number of "ab" minus the number of "ba" encountered so far cannot go above 1 or below -1. A finite automaton can track this and accept a word if the counter is 0 at the end.
• Dec 6th 2010, 09:57 AM
tom9999
Thanks very much i have now made a automata that accepts it so i know its regular.