Indietro

ⓘ Pumping lemma




                                     

ⓘ Pumping lemma

Il pumping lemma riguarda la presenza in ogni linguaggio context-free infinito di successioni di stringhe che presentano regolarità ben definite. In particolare ogni stringa sufficientemente lunga di un tale linguaggio contiene una o più porzioni che possono essere ripetute un numero arbitrario di volte ottenendo ancora una stringa appartenente al linguaggio.

Il pumping lemma fornisce una condizione necessaria ma non sufficiente affinché un linguaggio sia regolare o context-free, quindi può essere utilizzato per determinare che un particolare linguaggio non sia in una di queste classi, verificando che il linguaggio non soddisfi la condizione necessaria fornita dal pumping lemma.

                                     

1. Linguaggi regolari

Sia dato un linguaggio L regolare. Associata a L esiste una costante intera positiva n con la seguente proprietà. Sia z ∈ L, | z | ≥ n cardinalità di z ≥ n. Allora z può essere suddivisa in tre parti, z = uvw, con | uv | ≤ n, |v| > 0 con la proprietà che, per ogni i ≥ 0, la stringa uv i w appartiene a L.

Sia A un automa a stati finiti deterministico che riconosce il linguaggio L e sia n = |S|, con S insieme di stati dellautoma. Sia ora z una stringa accettata da A e tale che | z | > = n. Sia s 0. s |z| la sequenza di stati di A che porta allaccettazione di z. Per il principio della piccionaia esisterà un insieme di stati e comunque almeno uno dellautoma che viene attraversato più di una volta; sia s j il primo di questi stati. Sia u il minimo prefisso di z che porta lautoma nello stato s j, chiaramente si ha z = ux e | u | < n. A sua volta la stringa x può essere riscritta come x = vw, con v il minimo prefisso che riporta lautoma nello stato s j si è detto che esiste un ciclo nellautoma, w la stringa che porta lautoma nello stato s |z| ; chiaramente si ha | v | > = 1, | uv | = V N. Allora per il principio della piccionaia esiste un cammino di derivazione che espande più di una volta qualche non terminale, ad esempio A. Sia p il punto più vicino alla radice e sia q il punto più vicino alle foglie in cui viene espanso A.

Si può quindi riscrivere la stringa z come composta da cinque stringhe uvwxy. Inoltre è possibile sostituire il sottoalbero con radice in q nel punto p ottenendo una derivazione valida, cioè la stringa uwy, ma anche sostituire il sottoalbero con radice in p nel punto q in modo da ottenere uvvwxxy. Questo procedimento può essere iterato per ottenere tutte le stringhe del tipo uv i wx i y che sono generate dalla grammatica e pertanto appartengono al linguaggio.

                                     

2. Esempi

Un esempio classico consiste nel verificare che il linguaggio a n b n non è regolare. Infatti se lo fosse, la stringa z = a n/2 b n/2 potrebbe essere riscritta come uvw e uv i w apparterrebbe al linguaggio. Tuttavia, se v = ab, cioè contiene due caratteri diversi, la sua ripetizione porta ad una stringa ad esempio del tipo aaa abab bbb. Nel caso in cui v = a, cioè un solo carattere, la sua ripetizione porta ad un numero arbitrariamente lungo di ma non di b.

Come ulteriore esempio si può verificare che a n b n c n non è context-free. Analogamente a prima si hanno due casi: se le stringhe ripetute v e x contengono due caratteri diversi, la loro ripetizione genera una stringa con caratteri scambiati quindi non appartenente al linguaggio. Se invece tali stringhe contengono caratteri uguali, la loro ripetizione porta ad esempio a stringhe con un maggior numero di caratteri a e b rispetto a c.