Conversione di un’espressione regolare in automa

Vediamo come convertire una qualsiasi espressione regolare in un automa a stati finiti non deterministico.

Esempio

Prima di descrivere l’algoritmo, vediamo con un esempio di che cosa si tratta. Prendiamo questa espressione regolare: a(b|c)x^∗. A parole, descriveremmo il linguaggio generato dall’espressione come l’insieme delle parole che iniziano con la lettera «a», seguita da «b» oppure «c» e poi da un numero qualsiasi di lettere «x». Saremmo capaci di costruire un automa che accetti questo linguaggio? Certo, guarda:

Questo automa evidentemente accetta lo stesso linguaggio. Viene quindi da chiedersi se per ogni espressione regolare esista un automa che accetta il linguaggio corrispondente. Ebbene, sì.

Descrizione dell’algoritmo di conversione

Supponiamo di avere in ingresso un’espressione regolare R. Dalla parte precedente sulle espressioni regolari sappiamo che un’espressione regolare può avere in tutto sei forme diverse. Distinguiamo quindi sei casi:

1. R = a per un certo simbolo a ∈ Σ. Cioè l’espressione regolare è un solo simbolo dell’alfabeto Σ su cui lavoriamo. Un automa che accetta un solo simbolo a avrebbe questo aspetto:

   

2. R = ϵ, la parola vuota. Un automa che accetta la parola vuota avrebbe questo aspetto:

   

3. R = ∅, un’espressione regolare che genera il linguaggio vuoto. Un automa che riconosce un tale linguaggio è questo:

   

4. R = R₁ ∪ R₂, dove R₁, R₂ sono espressioni regolari. Sappiamo già che l’unione di linguaggi regolari è ancora un linguaggio regolare e che siamo in grado di costruire un automa che lo accetta. In altre parole, supponiamo di avere gli automi che riconoscono i linguaggi generati dalle espressioni R₁ e R₂ e con questi costruiamo un automa che accetta il linguaggio generato dall’espressione R₁ ∪ R₂. Esempio: se R₁ = a e R₂ = ϵ, seguendo la procedura otteniamo questo automa:

   

5. R = R₁ ∘ R₂, dove R₁, R₂ sono espressioni regolari. Lo stesso caso del punto precedente. La concatenazione di linguaggi regolari è un linguaggio regolare e sappiamo quindi costruire un automa che lo accetta. Quindi, se R₁ = a e R₂ = b, la concatenazione avrebbe questo aspetto:

   

6. $R=(R_1^{\ast })$, dove R₁ è un’espressione regolare. Sappiamo di nuovo che la chiusura di un linguaggio regolare è un linguaggio regolare. Quindi, se R = a^∗, l’automa avrebbe questo aspetto:

   

Applicando uno dopo l’altro questi punti convertiamo l’intera espressione regolare in un automa a stati finiti.

Un esempio completo

Proviamo a convertire l’espressione regolare (a|bc)^∗. Otteniamo via via questi automi:

L’automa risultante accetta il linguaggio generato dall’espressione regolare (a|bc)^∗. Naturalmente l’automa è terribilmente complicato e di sicuro esiste un automa molto più semplice che accetta lo stesso linguaggio. Possiamo usare l’algoritmo di conversione da NFA a DFA e poi fare la minimizzazione dell’automa.

Fonti

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools