Teorema (Pumping lemma): Sia $L$ un linguaggio regolare. Esiste allora una costante $n$ (dipendente da $L$) tale che ogni stringa $w\in L$ con lunghezza $|w|\geq n$ possa essere scomposta in tre stringhe, $w=xyz$, in modo che:
Di queste tre proprietà, la più importante è la terza: essa afferma sostanzialmente che a partire dalla stringa $xyz$ si possono costruire un’infinità di sitrnghe del linguaggio $L$, sostituendo $y$ con una potenza $k$-esima di $y$. La potenza di una stringa è definita come
$$ y^k = \underbrace{y...y}_k $$
con il caso base $y^n = \epsilon$.
Il nome “pumping lemma” deriva proprio dal fatto di poter “pompare”, “iniettare” quante copie si vogliono di $y$, ottenendo ancora stringhe del linguaggio.
In generale, dato un linguaggio regolare $L$, la costante $n$ per cui vale il pumping lemma non è unica. Si chiama costante di pumping di $L$, indicata con $N_L$, la più piccola costante $n$ per cui è verificato il pumping lemma.
Se il linguaggio $L$ contiene almeno una stringa $w\in L$ di lunghezza $|w|\geq N_L$, allora $L$ contiene infinite stringhe. Infatti, considerando la scomposizione $w = xyz$, siccome $y\neq \epsilon$ si ha che
$$ xy^0z \neq xyz \neq xy^2z \neq xy^3z \neq ... $$
e per la proprietà (3) del pumping lemma tutte queste infinite stringhe diverse appartengono a $L$:
$$ xy^0z, xyz, xy^3z, xy^3z, ..., xy^kz, ... \in L $$
Viceversa, se $L$ è un linguaggio finito, il lemma vale banalmente, semplicemente prendendo come costante di pumping $n$ un numero che sia maggiore della lunghezza di tutte le stringhe in $L$:
$$ N_L = \max\{|w| \ | \ w \in L\}+1 $$
Così, non esiste nessuna stirnga $w \in L$ tale che $|w|\geq n$, ma queste sono le uniche stringhe considerate dall’asserto del pumping lemma, che quindi risulta vuotamente verificato (si ha una quantificazione universale su un dominio vuoto).