Limitations of the Pumping Lemma

The Pumping Lemma is very unspecific as to where in the generated string the pumping is to occur. This can make some proofs quite difficult.

For example, to prove that { $a^mb^n\; \mid\;$ $m>n$ or $m$ is a prime number} is impossible by direct application of the Pumping Lemma.

In such cases, specialised versions, such as Parikh's Theorem, are required.