An important use of this lemma is to show that a language is not regular. (Remember, just because a language happens to be described in terms of an irregular grammar does not automatically preclude the possibility of describing the same language also by a regular grammar.) The idea is to assume that the language is regular, then arrive at a contradiction via this lemma.

An example of such a use of this lemma is afforded by the language $$ L = \{0^p 1^q 0^p \mid p,q > 0 \} $$ Let $n$ be the number whose existence is guaranteed by the lemma. Now, consider the word $W = 0^{n+1} 1^{n+1} 0^{n+1}$ . There must exist subwords $A,B,C$ such that $W = ABC$ and $B$ must be of length less than $n$ . The only possibilities are the following

1. $A = 0^u, B = 0^v, C = 0^{n+1-u-v} 1^{n+1} 0^{n+1}$
2. $A = 0^{n+1-u}, B = 0^u 1^v, C = 1^{n+1-v} 0^{n+1}$
3. $A = 0^{n+1} 1^v, B = 1^u, C = 1^{n+1-u-v} 0^{n+1}$
4. $A = 0^{n+1} 1^{n+1-v}, B = 1^v 0^u, C = 0^{n+1-u}$
5. $A = 0^{n+1} 1^{n+1} 0^u, B = 0^v, C = 0^{n+1-u-v}$

1. $AB^2C = 0^{n+1+v} 1^{n+1} 0^{n+1}$
2. $AB^2C = 0^{n+1} 1^v 0^u 1^{n+1} 0^{n+1}$
3. $AB^2C = 0^{n+1} 1^{n+1+u} 0^{n+1}$
4. $AB^2C = 0^{n+1} 1^{n+1} 0^u 1^v 0^{n+1}$
5. $AB^2C = 0^{n+1} 1^{n+1} 0^{n+1+u}$

It is easy to see that, in each of these five cases, $AB^2C \notin L$ . Hence $L$ cannot be a regular language.