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

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. 1.

   $A=0^{u},B=0^{v},C=0^{{n+1-u-v}}1^{{n+1}}0^{{n+1}}$

2. 2.

   $A=0^{{n+1-u}},B=0^{u}1^{v},C=1^{{n+1-v}}0^{{n+1}}$

3. 3.

   $A=0^{{n+1}}1^{v},B=1^{u},C=1^{{n+1-u-v}}0^{{n+1}}$

4. 4.

   $A=0^{{n+1}}1^{{n+1-v}},B=1^{v}0^{u},C=0^{{n+1-u}}$

5. 5.

   $A=0^{{n+1}}1^{{n+1}}0^{u},B=0^{v},C=0^{{n+1-u-v}}$

In these cases, $AB^{2}C$ would have the following form:

1. 1.

   $AB^{2}C=0^{{n+1+v}}1^{{n+1}}0^{{n+1}}$

2. 2.

   $AB^{2}C=0^{{n+1}}1^{v}0^{u}1^{{n+1}}0^{{n+1}}$

3. 3.

   $AB^{2}C=0^{{n+1}}1^{{n+1+u}}0^{{n+1}}$

4. 4.

   $AB^{2}C=0^{{n+1}}1^{{n+1}}0^{u}1^{v}0^{{n+1}}$

5. 5.

   $AB^{2}C=0^{{n+1}}1^{{n+1}}0^{{n+1+u}}$

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