Pumping Lemma per Linguaggi Liberi

Pumping Lemma per Linguaggi Liberi
Data una stringa w definita su un certo alfabeto, indichiamo con |w| la sua lunghezza,
ovvero il numero di caratteri da cui è composta. Per ogni intero n > 0, definiamo wn
come la stringa ottenuta concatenando n volte la stringa w.
Teorema (Pumping Lemma). Per ogni linguaggio libero L, esiste un intero positivo
costante H tale che ogni stringa z∈L di lunghezza |z| > H può essere decomposta nella
forma z = uvwxy tale che:
1. |vx| ≥ 1 (almeno una stringa tra v e x è diversa da ε);
2. |vwx| ≤ H;
3. per ogni intero k ≥ 1 vale che uvkwxky∈L.
Sfruttando il Pumping Lemma è possibile dimostrare che un certo linguaggio non è
esprimibile attraverso una grammatica libera dal contesto. Si consideri, ad esempio, il
seguente linguaggio: L = {anbncn | n ≥ 1}.
Teorema. Il linguaggio L = {anbncn | n ≥ 1} non è libero.
Dimostrazione. Supponiamo per assurdo che L sia libero. Applicando il Pumping
Lemma abbiamo che esiste una costante positiva H tale che la stringa z = aHbHcH∈L,
di lunghezza |z| = 3H > H, può essere decomposta nella forma z = uvwxy tale che:
1. |vx| ≥ 1 (almeno una stringa tra v e x è diversa da ε);
2. |vwx| ≤ H;
3. uv2wx2y∈L.
L’osservazione fondamentale, adesso, è che la stringa vwx non può contenere sia a
che c (infatti, se vwx contenesse contemporaneamente a e c, vorrebbe dire che essa
dovrebbe contenere tutte le H occorrenze di b, quindi si avrebbe |vwx| ≥ H+2, il ché
contrasta con il punto 2). Quindi, in uv2wx2y ci saranno o lo stesso numero di a
presenti in z, o lo stesso numero di c presenti in z, ovvero H. Dunque, poiché
|uv2wx2y| > 3H e uv2wx2y contiene esattamente H occorrenze di una tra le lettere a e c,
abbiamo che uv2wx2y non può appartenere a L. Ciò genera un assurdo con il punto 3,
dovuto al fatto di aver supposto che L fosse libero. Quindi, L non può essere un
linguaggio libero.