Il Pumping Lemma per i linguaggi context free, conosciuto anche come teorema uvwxy, dice:
“Sia L un linguaggi di tipo 2 su un alfabeto T. Allora esiste un intero positivo n, dipendente da L, tale che per ogni z ∈ L, se z> n , ci sono u, v, w, x, y ∈ T* per cui valgono le seguenti proprietà:
Dimostrazione pumping lemma per linguaggi context free
Sia G = <N, T, P, S> libero dal contesto per cui L =L(G) e sia p il numeri di simboli non terminali di G, consideriamo gli alberi di derivazione di G che hanno come radice un simbolo non terminale e che ammettono profondità <= p+1.
Otteniamo così un numero finito di alberi: sia n la lunghezza massima delle stringhe generate dai nodi foglia di questi alberi
Consideriamo adesso z∈L tale che z > n, z può essere generata solo da un albero di derivazione di profondità maggiore di p+1. Poiché p è il numero dei simboli non terminali di G questo cammino deve contenere almeno un simbolo non terminale che si ripete tra i nodi.
Esistono quindi due nodi N1 e N2
- N1 e N2 hanno la stessa etichetta, chiamiamola A
- N2 è discendente di N1
- Il cammino da N1 alla foglia è di lunghezza al più p + 1
Dimostramo le condizioni del Pumping Lemma per i linguaggi context free.
a) z = uvwxy
Il sotto albero di radice N2 genera una stringa w ∈ T* e quindi rappresenta una derivazione A —-> w.
Il sotto albero di radice N1, che comprende N2 tra i suoi nodi, genera una parola che contiene w come sotto stringa e la racchiude come vwx.
Allo stesso modo l’intero albero di computazione z(con radice S) che include N1, genera una stringa che allarga uvwxy, quindi z=uvwxy.
d) ∀ i ∈ ℕ, uv^iwx^iy ∈ L
Se adesso sfruttiamo che N1 e N2 ammettono la stessa etichetta A e rimpiazziamo w con vwz abbiamo uv^2wx^2y. Si prova così che uv^2wx^2y è generata da G, allo stesso modo si dimostra ∀ i > 0, uv^iwx^iy ∈ L.
b) l(vwx) <= n
Il sotto albero N1 ha profondità <= p + 1 quindi la stringa che il sotto albero genera, ovvero vwx, ha come lunghezza al più n per la definizione stessa di n
c) l(vx)>0
Se l(vx) = 0 e quindi v e x sono vuoti, z coincide con uwy ma questo contraddice la scelta dell’albero stesso.
