Pumping Lemma per i linguaggi liberi da contesto - Spiegazione

PUMPING LEMMA PER I LINGUAGGI LIBERI DA CONTESTO

Prima di poter definire il Pumping Lemma per i Linguaggi Liberi da contesto è necessario prima avere chiari i

concetti di albero di derivazione, lunghezza di un cammino lungo un albero, altezza di un albero e il principio

di sostituzione.

Un albero di derivazione è la rappresentazione univoca di una sequenza di produzioni. Ad esempio

→ (1) (2) (3)

considerando la grammatica G con P ={S Ha, H→ HS, H→ a} e volendo derivare la stringa aaaa è

1 1

possibile procedere in due modi:

(1) (2) (3) (1) (3)

1- S => Ha => HSa => aSa => aHaa => aaaa (derivazione sinistra espandendo il NT + a sinistra)

(1) (2) (1) (3) (3)

2- S => Ha => HSa => HHaa => Haaa => aaaa (derivazione destra espandendo il NT + a destra)

L’indecisione su quale sequenza sia stata applicata scompare se consideriamo l’albero di

derivazione della stringa aaaa secondo la grammatica G , infatti guardandolo non siamo

1

capaci di decidere se abbiamo espanso prima il NT H o S (nel punto indicato dalla freccia)

Da questo esempio possiamo dedurre che data una derivazione possiamo costruire un solo

albero di derivazione corrispondente, invece, dato un albero di derivazione esso corrisponderà

a più derivazioni in funzione dell’ordine in cui saranno espansi i non terminali.

La definizione di albero di derivazione (riportata sul libro) è la seguente:

є X

*

Sia G = (X , V, S , P) una grammatica libera da contesto e w una stringa derivabile da S in G. Dicesi albero

di derivazione l’albero T avene le seguenti proprietà:

1- la radice è etichettata con il simbolo iniziale S;

2- ogni nodo interno (nodo non foglia) è etichettato con un simbolo di V (è un non terminale);

nodo foglia è etichettato con un simbolo di X (un terminale) oppure con λ;

3- ogni , … , N

4- se un nodo N è etichettato con A, ad N ha k discendenti diretti (nodi figli) N , N , etichettati con

1 2 k

, … , A …A

i simboli A , A rispettivamente, allora la produzione A→A A deve appartenere a P;

1 2 k 1 2 k

la stringa w può essere ottenuta leggendo (e concatenando) le foglie dell’albero da sinistra a destra.

5-

Ora che abbiamo capito cosa è un albero di derivazione possiamo chiarire i concetti di lunghezza di un

cammino e profondità o altezza. La lunghezza di un cammino dalla radice ad una foglia è pari al numero di non

terminali su quel cammino. Ad esempio considerando l’albero precedente per la derivazione della stringa aaaa,

il cammino per la prima a (quella più a sinistra) è pari a 3 perché si incontra prima S, poi H ed ancora H, il

è 3 ( S H S ) ed infine il cammino dell’ultima

cammino per la seconda a è pari a 4 ( S H S H ), per la terza a a

L’altezza dell’albero (o profondità) è determinata dalla

(quella più a destra) è 1, infatti si incontra solo la S.

lunghezza del cammino più lungo, quindi la profondità dell’albero considerato precedentemente è 4.

Principio di sostituzione dei sottoalberi

Consideriamo la grammatica G libera da contesto con le seguenti produzioni P = {S→0B|1A; A→0|0S|1AA;

B→1|1S|0BB}, tale grammatica genera tutte e sole le stringhe che hanno un numero uguale di 1 e di 0

(esercizio 2.2 pag. 36 del libro). Consideriamo la stringa 0011, essa è ottenibile attraverso due derivazioni:

1- S => 0B => 00BB => 001B => 0011

2- S => 0B => 00BB => 00B1 => 0011

Come detto precedentemente il non determinismo scompare quando consideriamo l’albero di derivazione per

questa stringa. L’albero è riportato qui di seguito.

Adesso consideriamo il sottoalbero con radice nella B più in alto (racchiuso nel cerchio). Esso ha come

frontiera (insieme delle foglie) la stringa 011. Possiamo quindi affermare che partendo dal non terminale B è

possibile produrre la stringa 011. Poiché la grammatica G è libera da contesto possiamo sostituire un non

terminale con una sua produzione indipendentemente dal contesto, quindi possiamo sostituire liberamente

qualsiasi occorrenza di B con 011.

Effettuiamo questa sostituzione tra il sottoalbero con radice nella B in alto (c