Pumping lemma

Da Wikipedia, l'enciclopedia libera.

Il lemma pumping mostra che i linguaggi regolari e i linguaggi context-free hanno una struttura che presenta delle regolarità. In particolare alcune parti di una stringa possono essere ripetute un numero indefinito di volte ottenendo ancora una stringa appartenente al linguaggio.

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

Indice 1 Linguaggi regolari 2 Linguaggi liberi dal contesto 3 Esempi 4 Bibliografia

[modifica] Linguaggi regolari

Per approfondire, vedi la voce pumping lemma per i linguaggi regolari.

Sia dato un linguaggio L regolare. Sia , |z| >= n con n intero positivo. Allora z = uvw, con | uv | <= n, | v | >= 1 e 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. Si prenda la stringa z tale che | z | >= n, questa stringa viene accettata dall'automa e sia s₀ ... s_|z| la sequenza di stati 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 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.

[modifica] Linguaggi liberi dal contesto

Per approfondire, vedi la voce pumping lemma per i linguaggi liberi dal contesto.

Dato un linguaggio L context-free, sia . Sia n un intero positivo tale che | z | >= n, allora si può scrivere z = uvwxy con | vwx | <= n, | vx | >= 1 e 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).

Si consideri la stringa z appartenente al linguaggio, con | z | >= n = 2^V_N, da cui 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.

[modifica] Esempi

Un esempio classico consiste nel verificare che il linguaggio aⁿbⁿ non è regolare. Infatti se lo fosse, la stringa aaaabbbb 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 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.

[modifica] Bibliografia

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