ContentsPrevNext

Now for a example of the use of the Pumping Lemma

Say we want to recognize the language aⁿbⁿ, when n >= 0. In other words, strings in the language have the same number of a's and b's. So aabb, aaabbb and the empty string are in the language. So here is a first attempt at creating a fsa to do that:

Hmm, it certainly accepts every string in the language. But it also accepts things like: aab, abb ...

Time to try again.

Pumping 11