ContentsPrevNext

Can it be done?

The three attemps (and any other attempts to recognize aⁿbⁿ) can be divided into two types:

1. FSA that only recognize a finite number of strings (Such as attempt 2) since they do not have any repeats.
2. FSA that do repeat in some way (such as attempt 1 and 3) so they can accept an infinite number of strings.

The first type of fsa can not properly recognize a infinite language like aⁿbⁿ since there will always be strings that it does not accept. To find these just keep increasing the string size until it's length is greater than the number of states. This will not be accepted by the fsa.

The second type of fsa can not properly recognize aⁿbⁿ for a different reason. To understand the reason we need to remember the pumping lemma and some basic facts about fsa's. The first basic fact is that fsa have a set number of states. So let's call the number of states in the fsa P. Now, we know if we give a fsa at a string with the same number of symbols (or more) as it has states, then it will repeat. So, lets give it the string a^Pb^P. In other words, if the fsa had 2 states, then it would be given the string aabb. If it had 5 states, aaaaabbbbb. Then, since we know that there must be a repeat, we know that part of the string of a's must be a portion of the y part. However, based on the pumping lemma, we also know that the y part can be repeated or omitted. However, this means that the fsa will accept invalid strings. For example, if the y part is aa and the string aaaaabbbbb is accepted, then the string aaabbbbb will also be accepted and the string aaaaaaabbbbb will be accepted. Neither is in the language.

Pumping 15