È una condizione necessaria (ma non sufficiente) per dimostrare che un linguaggio è di tipo 2 o di tipo 3, si basa sul concetto che in un linguaggio infinito a un certo punto deve essere presente una stringa motore che viene ripetuta $n$ volte (pompata) per ottenere nuove stringhe del linguaggio
Se $L$ e un linguaggio di tipo 2 esiste un intero $N$ tale che per ogni stringa $z: len(z)\geq N$ per cui:
- $z$ e scomponibile in 5 parti $z = uvwxy$
- $vwx \leq N$
- $\vert vx \vert \geq 1$
Dove le componenti $v$ $x$ possono essere ripetute (pompate) per ottenere le altre frasi del linguaggio
$$uv^iwx^iy \in L \forall i \geq 0$$Linguaggi di tipo 3 #
Esiste una variante del teorema per linguaggi di tipo 3
Se $L$ e un linguaggio di tipo 3 esiste un intero $N$ tale che per ogni stringa $z: len(z)\geq N$ per cui:
- $z$ e scomponibile in 3 parti $z = xyw$
- $y\leq N$
- $\vert y\vert \geq 1$
Dove la componente centrale $y$ può essere ripetuta (pompata) per ottenere le altre frasi del linguaggio
$$xy^iw \in L \forall i \geq 0$$