Nella pratica quotidiana le espressioni regolari sono uno strumento per cercare testo. In teoria della computazione hanno un ruolo più preciso: sono un linguaggio formale per descrivere linguaggi, con una sintassi minima e una semantica rigorosa. Il teorema di Kleene afferma che le espressioni regolari descrivono esattamente i linguaggi riconosciuti dagli automi a stati finiti. Due formalismi nati con scopi diversi, uno dichiarativo e uno operativo, coincidono.
Le espressioni regolari in senso teorico
Sull'alfabeto Σ, le espressioni regolari si definiscono per induzione:
- ∅ è un'espressione regolare e denota il linguaggio vuoto;
- ε denota il linguaggio che contiene solo la stringa vuota;
- ogni simbolo a ∈ Σ denota il linguaggio {a};
- se R e S sono espressioni regolari, lo sono anche R | S (unione), RS (concatenazione) e R* (stella di Kleene, cioè zero o più ripetizioni).
Tutto il resto è abbreviazione. R+ equivale a RR*, R? equivale a R | ε. Molti costrutti dei motori di ricerca testuale moderni, come i riferimenti all'indietro, escono da questo quadro e possono descrivere linguaggi non regolari: vale la pena ricordarlo quando si confrontano teoria e strumenti.
L'enunciato
Il teorema di Kleene ha due direzioni:
- Per ogni espressione regolare R esiste un automa finito che riconosce L(R).
- Per ogni automa finito M esiste un'espressione regolare che denota L(M).
Poiché sappiamo già che NFA e DFA sono equivalenti, basta lavorare con l'automa più comodo in ciascuna direzione.
Da espressione ad automa: la costruzione di Thompson
La prima direzione si dimostra per induzione sulla struttura dell'espressione, costruendo un NFA con ε-transizioni. Ogni automa costruito ha un solo stato iniziale e un solo stato finale, il che rende facile incollare i pezzi.
- Simbolo a: due stati collegati da una transizione etichettata a.
- ε: due stati collegati da una ε-transizione.
- ∅: due stati senza alcuna transizione.
- Unione R | S: un nuovo stato iniziale con ε-transizioni verso gli iniziali di R e di S, e ε-transizioni dai loro finali verso un nuovo stato finale.
- Concatenazione RS: una ε-transizione dal finale di R all'iniziale di S.
- Stella R*: un nuovo iniziale e un nuovo finale; ε dall'iniziale al finale (zero ripetizioni), ε dall'iniziale all'iniziale di R, ε dal finale di R all'iniziale di R (ripetere) e al nuovo finale (uscire).
Il numero di stati cresce in modo lineare rispetto alla lunghezza dell'espressione: ogni operatore aggiunge al massimo due stati. Da qui si può passare a un DFA con la costruzione dei sottoinsiemi, se serve.
Da automa a espressione: l'eliminazione degli stati
La seconda direzione è meno intuitiva. Il metodo più leggibile è l'eliminazione degli stati su un automa generalizzato, in cui le transizioni sono etichettate con espressioni regolari invece che con singoli simboli.
- Si aggiungono un nuovo stato iniziale e un nuovo stato finale unico, collegati con ε all'automa originale.
- Si sceglie uno stato interno q da eliminare.
- Per ogni coppia di stati p e r con un arco p → q etichettato A, un eventuale cappio su q etichettato B e un arco q → r etichettato C, si aggiunge (o si unisce con |) un arco p → r etichettato A B* C.
- Si rimuove q e si ripete finché restano solo iniziale e finale.
L'etichetta dell'unico arco rimasto è l'espressione cercata.
Un esempio
Prendiamo il DFA su {0, 1} con due stati, A iniziale e B accettante: da A con 0 si resta in A, da A con 1 si va in B, da B con 1 si resta in B, da B con 0 si torna in A. Riconosce le stringhe che terminano con 1.
Aggiungiamo S → A con ε e B → F con ε. Eliminiamo A: l'arco S → A è ε, il cappio su A è 0, l'arco A → B è 1, quindi S → B diventa 0*1. C'è anche il percorso B → A → B: arco B → A con 0, cappio 0, arco A → B con 1, che si unisce al cappio esistente su B: il cappio diventa 1 | 00*1.
Eliminiamo B: S → F diventa 0*1 (1 | 00*1)*. È un'espressione corretta per «stringhe che terminano con 1», anche se non la più compatta: (0 | 1)*1 descrive lo stesso linguaggio. L'eliminazione degli stati garantisce la correttezza, non l'eleganza, e l'ordine di eliminazione influisce molto sulla lunghezza del risultato.
Perché conta
Il teorema di Kleene ha conseguenze concrete:
- Chiusura: i linguaggi regolari sono chiusi per unione, concatenazione e stella in modo evidente dalle espressioni, e per complemento e intersezione in modo evidente dai DFA. Combinando le due viste si ottiene la chiusura per tutte queste operazioni.
- Strumenti: i generatori di analizzatori lessicali partono da espressioni regolari e producono automi; è esattamente la prima direzione del teorema.
- Confronto: per stabilire se due espressioni regolari sono equivalenti si convertono entrambe in DFA minimi e si confrontano. Il problema è decidibile, anche se nel caso peggiore il costo cresce rapidamente.
In sintesi
- Le espressioni regolari teoriche usano solo ∅, ε, simboli, unione, concatenazione e stella.
- Il teorema di Kleene dice che descrivono esattamente i linguaggi riconosciuti dagli automi finiti.
- La costruzione di Thompson trasforma un'espressione in un NFA con un numero lineare di stati.
- L'eliminazione degli stati trasforma un automa in espressione, corretta ma non sempre compatta.
- Unire le due prospettive rende semplice dimostrare le proprietà di chiusura dei linguaggi regolari.
