Il pumping lemma è una cavolata, espressa in una maniera complicata perché formale.
Ogni stringa sposta l'automa da uno stato all'altro, ma se ci sono più lettere che stati è ovvio che perché la stringa sia riconosciuta bisogna che ripeta più volte il passaggio attraverso alcuni stati.
Gli angolofoni lo chiamano principio dei buchi della piccionaia, noi principio dei cassetti, ma il senso non cambia.
In pratica quindi:
- for each i ≥ 0, xyiz ∈ A significa che A contiene xz, xyz, xyyz, xyyyz, xyyyyz...
- |y| > 0 significa, banalmente, che non posso scegliere ε come y, cioè devo avere un y che contiene qualcosa. Al limite, lo ripeto zero volte...
- |xy| ≤ p significa che o p si ferma a x oppure è lungo almeno xy
Da questi tre punti si evince anche che:
- x e z possono essere ε
- se p > 0, allora o x o y devono essere diversi da ε