Dimostrare che un linguaggio è regolare è spesso facile: basta esibire un automa o un'espressione regolare. Dimostrare che non lo è richiede invece un argomento generale, che valga contro qualunque automa possibile. Il pumping lemma è lo strumento classico per farlo. È anche uno degli argomenti in cui gli studenti sbagliano di più, quasi sempre per un errore di logica sui quantificatori più che di matematica.
L'intuizione: un automa finito deve ripetere uno stato
Sia M un DFA con p stati. Se M legge una stringa di lunghezza almeno p, attraversa almeno p + 1 stati (contando quello iniziale). Per il principio dei cassetti, almeno uno stato compare due volte. Il tratto di input letto tra le due visite forma un ciclo: l'automa parte da uno stato e ci ritorna.
Ma un ciclo si può percorrere zero volte, una volta o cento volte, e l'automa finisce comunque nello stesso stato alla fine della stringa. Quindi se la stringa originale era accettata, lo sono anche tutte le versioni «pompate».
L'enunciato
Se L è regolare, esiste un intero p ≥ 1 (la lunghezza di pumping) tale che ogni stringa s ∈ L con |s| ≥ p si può scrivere come s = xyz con:
- |y| ≥ 1 (il ciclo non è vuoto);
- |xy| ≤ p (il ciclo compare entro i primi p simboli);
- xyⁱz ∈ L per ogni i ≥ 0.
La seconda condizione deriva dal fatto che la prima ripetizione di stato avviene necessariamente entro i primi p simboli letti. È la condizione più utile nelle dimostrazioni, perché vincola la posizione di y.
La struttura logica
L'enunciato ha la forma: esiste p, per ogni s, esiste una scomposizione, per ogni i. Per dimostrare che L non è regolare si nega tutto, e i quantificatori si scambiano:
per ogni p, esiste s ∈ L con |s| ≥ p tale che, per ogni scomposizione s = xyz che rispetti le condizioni 1 e 2, esiste un i con xyⁱz ∉ L.
Conviene pensarlo come un gioco a due:
- l'avversario sceglie p;
- tu scegli la stringa s, che può dipendere da p;
- l'avversario sceglie la scomposizione xyz, rispettando |y| ≥ 1 e |xy| ≤ p;
- tu scegli i e mostri che xyⁱz esce dal linguaggio.
Se hai una strategia vincente qualunque cosa faccia l'avversario, il linguaggio non è regolare.
Esempio 1: aⁿbⁿ
Sia L = {aⁿbⁿ : n ≥ 0}. Dato p, scegliamo s = aᵖbᵖ. Qualunque scomposizione con |xy| ≤ p ha x e y fatti solo di a, perché i primi p simboli sono tutte a. Quindi y = aᵏ con k ≥ 1. Pompando con i = 2 si ottiene aᵖ⁺ᵏbᵖ, che ha più a che b e non appartiene a L. Il linguaggio non è regolare.
Notate come la scelta di s abbia fatto tutto il lavoro: mettendo le a all'inizio e sfruttando la condizione 2, abbiamo eliminato ogni possibilità di scelta per l'avversario.
Esempio 2: stringhe di lunghezza quadrata
Sia L = {aⁿ : n è un quadrato perfetto}. Dato p, scegliamo s = a^(p²). L'avversario sceglie y = aᵏ con 1 ≤ k ≤ p. Con i = 2 si ottiene una stringa di lunghezza p² + k. Ma p² < p² + k ≤ p² + p < (p + 1)², quindi la lunghezza cade strettamente tra due quadrati consecutivi e non è un quadrato. La stringa esce da L.
Esempio 3: palindromi
Sia L l'insieme dei palindromi su {a, b}. Scegliamo s = aᵖbaᵖ. Di nuovo y è composto solo da a della prima metà. Con i = 0 si toglie qualche a a sinistra e la stringa diventa aᵖ⁻ᵏbaᵖ, che non è più palindroma.
Errori tipici
- Scegliere un p specifico. Non si può dire «prendiamo p = 5»: p è scelto dall'avversario e va trattato come generico.
- Scegliere la scomposizione. Non si decide dove sta y: bisogna considerare tutte le scomposizioni ammesse.
- Stringa troppo corta o fuori dal linguaggio. s deve appartenere a L e avere lunghezza almeno p.
- Usare il lemma per dimostrare la regolarità. Il lemma è solo una condizione necessaria. Esistono linguaggi non regolari che soddisfano comunque le condizioni di pumping; per quelli serve uno strumento più forte, come il teorema di Myhill-Nerode.
Alternative e scorciatoie
Spesso conviene sfruttare le proprietà di chiusura. Se L fosse regolare e R è regolare, anche L ∩ R sarebbe regolare. Per esempio, il linguaggio delle stringhe con lo stesso numero di a e di b, intersecato con a*b*, dà esattamente aⁿbⁿ; poiché quest'ultimo non è regolare, non lo è nemmeno il linguaggio di partenza. Una riga invece di una dimostrazione intera.
In sintesi
- Un automa con p stati, leggendo almeno p simboli, ripete uno stato e forma un ciclo che si può pompare.
- Il lemma garantisce una scomposizione xyz con |y| ≥ 1, |xy| ≤ p e xyⁱz nel linguaggio per ogni i.
- Per dimostrare la non regolarità si gioca contro un avversario che sceglie p e la scomposizione.
- La scelta furba della stringa, sfruttando |xy| ≤ p, è quasi sempre la chiave.
- Il lemma è solo necessario: per alcuni casi servono Myhill-Nerode o le proprietà di chiusura.
