The Pumping Lemma (Theorem)

The Pumping Lemma says if $L\subseteq {\Sigma }^{\ast }$ is a regular language then there is some $p>0$ such that every word $w\in L$ of length $|w|\ge p$ can be written in the form $w=xyz$ for $x,y,z\in {\Sigma }^{\ast }$ such that:

• If $|xy|\le p$ and $|y|>0$,
• then $x{y}^{n}z\in L$ for all $n\ge 0$.