Conversione di un automa in espressione regolare

Vediamo come convertire un qualsiasi automa a stati finiti in un’espressione regolare.

Descrizione dell’algoritmo

In ingresso abbiamo un NFA A. Come prima cosa ne ricaviamo un GNFA. Nella seconda fase, a ogni passo eliminiamo uno stato, modifichiamo in modo opportuno la funzione di transizione e ripetiamo, finché non restano solo due stati: quello iniziale e quello finale. Tra loro ci sarà un arco etichettato con un’espressione regolare, che è il risultato dell’intero algoritmo. L’intera procedura consiste quindi soprattutto nell’eliminare uno stato e poi correggere l’automa in modo da ottenerne uno equivalente.

Eliminazione di un solo stato

Vediamo con un semplice esempio come si elimina uno stato. Supponiamo che una parte del nostro automa abbia questo aspetto:

dove R_i sono espressioni regolari. Come sarebbe l’automa se eliminassimo lo stato q_r? Possiamo immaginare di trovarci nello stato q_i e di chiederci quali parole possiamo generare in questo tratto. Se andiamo da q_i direttamente a q_j, saranno tutte le parole che corrispondono all’espressione regolare R₄.

Se invece andiamo nello stato q_r, possiamo generare le parole della forma R₁. Nello stato q_r però possiamo ciclare con l’espressione regolare R₂, quindi possiamo generare le parole della forma $R_1\circ (R_2^{\ast })$. E poiché dallo stato q_r possiamo ancora arrivare allo stato q_j, aggiungiamo anche l’espressione regolare R₃. In totale, per questa via possiamo ottenere le parole della forma $R_1\circ (R_2^{\ast })\circ R_3$.

Ora sappiamo che da questa parte dell’automa possono nascere parole della forma R₄ oppure della forma $R_1\circ (R_2^{\ast })\circ R_3$. Naturalmente possiamo scriverlo sotto forma di espressione regolare come $(R_4)|(R_1\circ (R_2^{\ast })\circ R_3)$.

Ora possiamo eliminare facilmente lo stato q_r, lasciando solo i due stati q_i e q_j, e al posto di R₄ scriviamo l’espressione appena calcolata:

Eseguiamo questa procedura per ogni arco da ogni stato q_i a un qualche stato q_j, compresi i cappi, cioè anche il caso in cui q_i = q_j.

Dopo aver eliminato uno stato otteniamo un automa equivalente, cioè un automa che riconosce lo stesso linguaggio.

L’algoritmo completo

In ingresso abbiamo un NFA A = ⟨Q, Σ, δ, q₀, F⟩.

1. Convertiamo l’NFA A in un GNFA Z = ⟨Q′, Σ, δ′, q₀′, q_f′⟩. D’ora in poi indichiamo con la lettera k il numero di stati di Z.
2. Se k = 2, l’algoritmo termina e sull’arco tra lo stato iniziale e lo stato finale c’è l’espressione regolare cercata.
3. Se k>2, scegliamo uno stato qualsiasi q_r diverso dallo stato iniziale e da quello finale, cioè q_r ≠ q₀′ e q_r ≠ q_f′. Poi costruiamo un nuovo GNFA Z′ = ⟨Q′′, Σ, δ′′,q₀′,q_f′⟩ per il quale vale: $$Q^{\prime \prime }=Q^{\prime }\setminus \left\{q_r\right\}$$ e per ogni q_i ∈ Q′′ ∖ {q_f′} e per ogni q_j ∈ Q′′ ∖ {q₀′} sia $${\delta }^{\prime \prime }(q_i,q_j)=(R_4)|(R_1(R_2^{\ast })R_3),$$ dove R₁ = δ′(q_i,q_r), R₂ = δ′(q_r,q_r), R₃ = δ′(q_r, q_j), R₄ = δ′(q_i, q_j). Poi continua con il passo 2.

Esempio

Prendiamo in ingresso questo automa a stati finiti:

Per prima cosa lo convertiamo in un GNFA (le transizioni inutili ∅ non le disegniamo):

Ora applichiamo la seconda parte dell’algoritmo ed eliminiamo un nodo. Cominciamo con il nodo q₂. Eliminiamo il nodo q₂ e aggiungiamo una transizione dallo stato q₁ allo stato q_f. La etichettiamo con b(a|b)^∗, perché dal nodo q₁ arriviamo allo stato q₂ con le parole della forma b, poi possiamo ciclare con a|b, ottenendo (a|b)^∗, e infine con la ε-transizione ci spostiamo in q_f. Inoltre vale b(a|b)^∗ϵ = b(a|b)^∗. Otteniamo l’automa:

Resta da eliminare l’ultimo stato, q₁. Aggiungiamo un arco dallo stato q_s allo stato q_f. Come lo etichettiamo? Nello stato q₁ arriviamo con una ε-transizione, che possiamo tralasciare subito. Poi possiamo ciclare con a, quindi otteniamo l’espressione regolare a^∗. Infine, attraverso l’arco arriviamo a q_f, quindi concateniamo l’espressione con b(a|b)^∗. L’arco è quindi etichettato con l’espressione regolare a^∗ b(a|b)^∗.

L’automa ha ormai solo due stati, quindi l’algoritmo termina. Sull’arco c’è l’espressione regolare cercata.

Fonti

• L’esempio e la descrizione dell’algoritmo provengono da M. Sipser: Introduction to the Theory of Computation