pumping lemma per linguaggi regolari

ecco qui uno strumento utile a dimostrare che determinati linguaggi non sono regolari

è una semplificazione di un lemma analogo per i linguaggi liberi da contesto

pumping lemma: se L è un linguaggio regolare, esiste n > 0 tale che ogni stringa w in L che abbia |w| ≥ n è scomponibile in tre stringhe w = xyz tali che

y ≠ ε
|xy| ≤ n
per ogni k ≥ 0 la stringa xy ^kz è in L

nocciolo della dimostrazione: ogni linguaggio regolare è riconoscibile da un DFA, dotato di un insieme finito di stati; ogni stringa accettata di lunghezza maggiore o uguale al numero di stati etichetta un cammino, nel grafo del DFA, che attraversa più volte uno stesso stato

si noti l'alternanza dei quantificatori, universale ed esistenziale, nell'enunciato del pumping lemma: ciò permette di impostarne l'uso come "gioco a due" per dimostrare la non regolarità di linguaggi formali

applicazioni del pumping lemma

esempio: il linguaggio L = { aⁿbⁿ | n > 0 } non è regolare

sia n la costante nell'enunciato del pumping lemma, scegliamo la stringa w = aⁿbⁿ
comunque si effettui una scomposizione di w in w = xyz che rispetti i vincoli posti nell'enunciato del pumping lemma, sappiamo che il prefisso xy è costituito solo da simboli a e che il suo suffisso y non è vuoto, dunque scegliendo k = 0, o anche k ≥ 2, otteniamo una stringa che per il pumping lemma dovrebbe essere in L, se questo fosse regolare, ma invece non gli appartiene, dunque L non è regolare

in modo del tutto simile si dimostra la non regolarità del linguaggio costituito dalle stringhe in ciascuna delle quali i due simboli dell'alfabeto hanno lo stesso numero di occorrenze, indipendentemente dall'ordine

sarebbe difficile, invece, dimostrare per questa via che non è regolare il linguaggio delle stringhe in ciascuna delle quali i due simboli hanno un diverso numero di occorrenze

tuttavia, tale linguaggio è il complemento di quello precedente, e poiché la classe dei linguaggi regolari è chiusa per complementazione...

problemi di decisione per linguaggi formali

i seguenti problemi di decisione acquistano interesse per linguaggi formali di cardinalità infinita, ma specificati da una descrizione finita (quali, ad es., grammatiche formali, FSA, espressioni regolari)

vacuità del linguaggio descritto
appartenenza di una stringa data al linguaggio descritto
equivalenza di due descrizioni di linguaggi

tutti e tre questi problemi sono decidibili per la classe dei linguaggi regolari

esistono cioè algoritmi che terminano sempre con la risposta corretta, sia essa positiva o negativa, quando il linguaggio è descritto da un FSA o da una espressione regolare

purtroppo non lo sono, invece, per le classi di linguaggi più ampie di questa nella gerarchia di Chomsky

vacuità di linguaggi regolari

grazie alla convertibilità fra i vari tipi di FSA, e fra questi e le espressioni regolari, per mostrare la decibilità dei problemi suddetti nella classe dei linguaggi regolari è sufficiente esibire un algoritmo risolutivo, per ciascuno di essi, con riferimento a uno solo dei vari tipi di descrizione di linguaggi regolari

il problema della vacuità è tuttavia di semplice soluzione per tutti i suddetti tipi di descrizione dei linguaggi regolari:

per FSA, il problema equivale a quello dell'appartenenza di un stato accettante all'insieme degli stati raggiungibili dallo stato iniziale; questo insieme è facilmente determinabile da un algoritmo ricorsivo per la raggiungibilità nei grafi, e poiché sia questo insieme che quello degli stati accettanti sono insiemi finiti, la vacuità della loro intersezione è decidibile
per espressioni regolari, un algoritmo risolutivo del problema in questione può procedere per induzione sulla struttura dell'espressione, tenendo conto delle proprietà della costante ∅ nell'algebra delle espressioni regolari

appartenza a linguaggi regolari

la decibilità di questo problema discende direttamente dalla simulabilità dell'elaborazione della stringa data da parte di un DFA

basta verificare se lo stato di arrivo dell'automa, dopo la sequenza di transizioni determinata dalla stringa a partire dallo stato iniziale, sia uno stato accettante

l'algoritmo indicato è semplice ed efficiente (tempo di esecuzione lineare nella dimensione della stringa) quando il linguaggio è descritto da un DFA

se il linguaggio è descritto da un NFA, con o senza ε-transizioni, la preliminare conversione in un DFA equivalente può richiedere un tempo di esecuzione esponenziale nella dimensione dell'automa originale

un'alternativa più efficiente consiste nella simulazione del NFA, o ε-NFA, tenendo traccia dell'insieme di stati raggiungibile da ciascuno stato per un dato simbolo nella stringa, nel corso della sua elaborazione, con tempo di esecuzione quadratico nel numero di stati

se l'automa ha ε-transizioni, ad ogni passo occorre calcolare la ε-chiusura dell'insieme di stati raggiunti

infine, nel caso di un'espressione regolare, la si può convertire in un ε-NFA equivalente in tempo lineare nel numero degli stati, e procedere quindi come sopra

equivalenza di automi

decidere se due descrizioni di linguaggi regolari denotino lo stesso linguaggio è un problema più impegnativo degli altri due esaminati sopra

il seguente concetto è la chiave di volta della sua soluzione:

equivalenza di stati di un DFA:

...

minimizzazione di DFA

...

temi per ulteriori approfondimenti

Complessità delle conversioni di FSA ed espressioni regolari
la mera esistenza di algoritmi che permettono la costruzione di un DFA equivalente a un NFA o ε-NFA o espressione regolare, e viceversa, non basta a garantire la pratica fattibilità di tali conversioni in tutti i casi; è rilevante in proposito l'analisi della complessità computazionale degli algoritmi in questione, anche al fine di scegliere, quando esistano più opzioni, quella più conveniente; il tema è trattato nella sez. 4.3.1 del testo (Hopcroft, Motwani, Ullman, 2009), che presenta anche un utile riepilogo dei vari algoritmi di conversione

Pumping lemma e problemi decibili per linguaggi regolari

Lezione 24 di Fondamenti di informatica

Indice