Pumping lemma

Il pumping lemma riguarda la presenza in ogni linguaggio context-free infinito (e in particolare in ogni linguaggio regolare 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.

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 ⁱ 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 dell'automa. Sia ora z una stringa accettata da A e tale che |z| >= n. Sia s₀ ... s_|z| la sequenza di stati di A che porta all'accettazione di z. Per il principio della piccionaia esisterà un insieme di stati (e comunque almeno uno) dell'automa che viene attraversato più di una volta; sia s_j il primo di questi stati. Sia u il minimo prefisso di z che porta l'automa 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 l'automa nello stato s_j (si è detto che esiste un ciclo nell'automa), w la stringa che porta l'automa nello stato s_|z|; chiaramente si ha |v| >= 1 , |uv| <= n e z = uvw.

Si ha che anche per ogni i≥o la stringa uv ⁱ w viene riconosciuta dall'automa perché ogni computazione termina in uno stato di accettazione. Infatti T(s₀, uv ⁱ w) = T(s _j, v ⁱ w)= T(s _j, v ^i-1 w) = ... = T(s _j, w) = s _|z|.

Pertanto la stringa appartiene al linguaggio.

Linguaggi liberi dal contesto

Dato un linguaggio L context-free, esiste una costante intera positiva n con la seguente proprietà. Sia z ∈ L con |z| ≥ n; allora si può suddividere z = uvwxy con |vwx| ≤ n, |vx| ≥ 1 tali che, per ogni i≥0, uv ⁱ wx ⁱ y appartiene a L.

Sia G una grammatica in forma normale di Chomsky che genera il linguaggio L. Si noti che i nodi interni dell'albero di derivazione (corrispondenti ai simboli non terminali) hanno grado 2 mentre le foglie (cioè i simboli terminali) hanno grado 1. Se s è una stringa generata dalla grammatica, si indica con h(s) l'altezza dell'albero, cioè la massima lunghezza di un qualsiasi cammino all'interno dell'albero di derivazione; si noti che |s |≤ 2^h(s).

Se V_N è l'insieme dei non terminali di G, si prenda n = 2^V_N. Sia ora z una generica stringa appartenente al linguaggio, con | z | >= n. Siccome l'albero di derivazione è binario, si ha h(z) >= 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 ⁱ wx ⁱ y che sono generate dalla grammatica e pertanto appartengono al linguaggio.

Esempi

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

Come ulteriore esempio si può verificare che aⁿbⁿcⁿ 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.

Bibliografia

Giorgio Ausiello; Fabrizio D'Amore; Giorgio Gambosi. Linguaggi, modelli, complessità. Milano, FrancoAngeli, 2003. ISBN 8846444701

Altri progetti

Wikimedia Commons contiene immagini o altri file su Pumping lemma

Portale Informatica

Portale Matematica