I linguaggi liberi dal contesto sono molto più espressivi dei regolari, ma hanno anch'essi dei limiti. Per dimostrare che un linguaggio non è libero dal contesto esiste una versione del pumping lemma adattata alle grammatiche. L'idea è simile a quella per gli automi finiti, ma la ripetizione riguarda una variabile in un albero sintattico, e le parti da pompare diventano due, che crescono insieme.
L'intuizione: una variabile si ripete lungo un cammino
Prendiamo una grammatica in forma normale di Chomsky, in cui ogni regola è A → BC oppure A → a. Gli alberi sintattici sono binari. Un albero binario di altezza h ha al massimo 2ʰ foglie, quindi una stringa molto lunga richiede un albero alto.
Se la grammatica ha k variabili e la stringa è abbastanza lunga, esiste un cammino dalla radice a una foglia con più di k variabili. Per il principio dei cassetti, una variabile R compare due volte su quel cammino. Il sottoalbero radicato nella R più in alto contiene quello radicato nella R più in basso.
Questa situazione permette due operazioni:
- sostituire il sottoalbero inferiore con una copia di quello superiore, ottenendo una stringa più lunga;
- sostituire il sottoalbero superiore con quello inferiore, ottenendo una stringa più corta.
Ciò che si aggiunge o si toglie sono due pezzi, uno a sinistra e uno a destra della parte centrale.
L'enunciato
Se L è libero dal contesto, esiste p ≥ 1 tale che ogni stringa s ∈ L con |s| ≥ p si può scrivere come s = uvxyz con:
- |vy| ≥ 1 (almeno uno dei due pezzi pompati non è vuoto);
- |vxy| ≤ p (la finestra pompata è corta);
- uvⁱxyⁱz ∈ L per ogni i ≥ 0.
Come nel caso regolare, per dimostrare la non appartenenza si gioca contro un avversario: lui sceglie p e la scomposizione, noi scegliamo la stringa e l'esponente i.
Esempio 1: aⁿbⁿcⁿ
Sia L = {aⁿbⁿcⁿ : n ≥ 0}. Dato p, scegliamo s = aᵖbᵖcᵖ.
La condizione |vxy| ≤ p è decisiva: una finestra di lunghezza al massimo p non può toccare sia le a sia le c, perché fra di esse ci sono p lettere b. Quindi v e y contengono al massimo due tipi di lettere fra i tre.
Pompando con i = 2, aumenta il numero di almeno un tipo di lettera, ma non di tutti e tre. I tre conteggi non sono più uguali, e la stringa esce da L. Inoltre, se v o y contengono lettere miste, come «ab», pompando si ottengono lettere fuori ordine. In ogni caso L non è libero dal contesto.
Esempio 2: la stringa ripetuta
Sia L = {ww : w ∈ {a, b}*}. È un caso istruttivo, perché il linguaggio molto simile {wwᴿ} dei palindromi pari è libero dal contesto.
Scegliamo s = aᵖbᵖaᵖbᵖ. Analizziamo dove può stare la finestra vxy, lunga al massimo p:
- se sta tutta nella prima metà, pompando con i = 0 si accorcia solo la prima metà; la stringa risultante non si può più dividere in due copie identiche;
- se sta tutta nella seconda metà, il ragionamento è simmetrico;
- se è a cavallo del centro, contiene solo b della prima metà e a della seconda; con i = 0 si ottiene una stringa della forma aᵖbʲaᵏbᵖ con j o k minori di p, che non è del tipo ww.
In tutti i casi si esce da L.
Le proprietà di chiusura
Spesso è più rapido usare le proprietà di chiusura. I linguaggi liberi dal contesto sono chiusi per:
- unione: S → S₁ | S₂;
- concatenazione: S → S₁S₂;
- stella: S → SS₁ | ε;
- intersezione con un linguaggio regolare: si simulano in parallelo un automa a pila e un automa finito, che non usa la pila.
Non sono invece chiusi per intersezione e complemento. Il controesempio classico: {aⁿbⁿcᵐ} e {aᵐbⁿcⁿ} sono entrambi liberi dal contesto, ma la loro intersezione è aⁿbⁿcⁿ, che non lo è. Poiché l'intersezione si esprime con unione e complemento, se ci fosse chiusura per complemento ci sarebbe anche per intersezione.
Una dimostrazione per chiusura
Sia L il linguaggio delle stringhe su {a, b, c} con lo stesso numero di a, b e c, in qualsiasi ordine. Se L fosse libero dal contesto, anche L ∩ a*b*c* lo sarebbe, perché a*b*c* è regolare. Ma quell'intersezione è esattamente aⁿbⁿcⁿ. Quindi L non è libero dal contesto. Nessuna scomposizione da analizzare.
Errori frequenti
- Dimenticare che v e y possono stare in zone diverse della stringa: vanno considerati tutti i posizionamenti della finestra.
- Non sfruttare |vxy| ≤ p, che è quasi sempre la condizione che rende la dimostrazione possibile.
- Pensare che superare il pumping lemma dimostri che il linguaggio è libero dal contesto: è una condizione necessaria, non sufficiente. Per casi difficili esistono strumenti più forti, come il lemma di Ogden.
In sintesi
- In un albero sintattico alto una variabile si ripete, e questo consente di pompare due parti insieme.
- Il lemma garantisce s = uvxyz con |vy| ≥ 1, |vxy| ≤ p e uvⁱxyⁱz nel linguaggio per ogni i.
- aⁿbⁿcⁿ e {ww} non sono liberi dal contesto.
- I linguaggi liberi dal contesto sono chiusi per unione, concatenazione, stella e intersezione con regolari.
- Non sono chiusi per intersezione e complemento, e questo fornisce dimostrazioni rapide.
