Now for a example of the use of the Pumping Lemma

Say we want to recognize the language anbn, 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:

This applet requires the Java Plug-In version 1.3.

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

Time to try again.

Pumping 11