Simulazione di un automa non deterministico

Se abbiamo un automa non deterministico e vogliamo sapere se accetta una data parola, possiamo convertirlo in un automa deterministico, possiamo andare per tentativi, oppure possiamo usare un algoritmo che simula il funzionamento dell’NFA.

Il principio dell’algoritmo

Illustriamo il principio con un esempio adatto. Prendiamo questo automa:

Si tratta di un automa a stati finiti non deterministico che accetta un certo linguaggio. Per ora non ci interessa affatto quale. Vediamo come può svolgersi il calcolo di un automa di questo tipo sulla parola in ingresso 11001. Il ragionamento è questo: elaboriamo un simbolo della parola e guardiamo in quali stati possiamo andare grazie alle transizioni multiple per lo stesso simbolo. Ci ricordiamo tutti questi stati e nel passo successivo supponiamo di trovarci «in tutti questi stati contemporaneamente»; ci interessa allora dove possiamo arrivare da questi stati.

Ci ricordiamo così un insieme di stati in cui possiamo trovarci e la parte non ancora letta della parola. All’inizio abbiamo quindi la coppia ⟨{q₀}, 11001⟩. Partiamo dallo stato q₀ (stato iniziale) e in ingresso c’è la parola 11001. L’automa si presenta così; in rosso e in grassetto è evidenziato lo stato in cui ci troviamo:

Il primo simbolo è 1; dallo stato q₀ c’è una sola transizione per il simbolo 1, quindi arriviamo nello stato q₁. Ci ricordiamo la coppia ⟨{q₁}, 1001⟩. L’automa si presenta così:

Andiamo avanti. La parte non letta della parola è 1001, quindi cerchiamo di nuovo le transizioni per 1. Ora sono due: una che torna nello stato q₀ e una verso lo stato q₃. Questa volta andiamo in entrambi gli stati contemporaneamente. Ci ricordiamo quindi la coppia ⟨{q₀, q₃}, 001⟩.

Qual è la logica? Sappiamo che esiste un cammino che, con la parola 11, porta dallo stato iniziale sia nello stato q₃ sia nello stato q₀. Non sappiamo ancora quale ramo ci servirà, quindi ci ricordiamo semplicemente entrambi. Andiamo avanti. In ingresso c’è il simbolo 0. Ora dobbiamo guardare sia le transizioni da q₀ sia quelle da q₃. Da q₀ partono transizioni verso gli stati q₁ e q₂, da q₃ parte una transizione di nuovo verso q₁. Teniamo conto di tutti questi stati e otteniamo la coppia ⟨{q₁, q₂}, 01⟩:

In questo passo, però, non abbiamo ancora finito. Vediamo che dallo stato q₂ parte una ε-transizione verso lo stato q₄. Sappiamo che una ε-transizione si può percorrere «in qualsiasi momento», senza leggere un altro carattere. In altre parole: senza leggere il simbolo successivo della parola in ingresso, possiamo ancora spostarci nello stato q₄. Aggiungiamo quindi lo stato q₄ agli stati in cui possiamo trovarci: ⟨{q₁, q₂, q₄}, 01⟩. L’automa lo coloreremmo così:

Poi in ingresso c’è 0. Guardiamo dove possiamo spostarci dai tre stati in cui ci troviamo. Da q₁ non possiamo andare da nessuna parte, perché manca la transizione per 0: il calcolo in questo ramo termina. Anche da q₄ non arriviamo da nessuna parte. Da q₂ torniamo nello stato q₂. Ma poiché da q₂ parte di nuovo una ε-transizione verso q₄, possiamo arrivare anche nello stato q₄. Dall’insieme di stati {q₁, q₂, q₄} con il simbolo 0 possiamo quindi arrivare all’insieme di stati {q₂, q₄} e otteniamo la coppia ⟨{q₂, q₄}, 1⟩:

Infine in ingresso c’è il simbolo 1. Da q₂ non arriviamo da nessuna parte e il calcolo in questo ramo termina. Da q₄ invece arriviamo negli stati q₃ e q₅. Otteniamo la coppia ⟨{q₃, q₅}, ε⟩:

L’automa ha ora letto tutta la parola e «si trova» in due stati: q₃, q₅. Poiché almeno uno dei due è uno stato finale, l’automa accetta la parola 11001.

L’algoritmo

Per prima cosa ci serve una funzione che prenda come parametro un insieme di stati e calcoli in quali altri stati si può arrivare con le ε-transizioni. L’ingresso è quindi l’automa ⟨Q, Σ, δ, q₀, F⟩ e un insieme di stati States; l’uscita è un sovrainsieme di questi stati, formato dagli stati raggiungibili con le ε-transizioni. Questa operazione la chiameremo ε-chiusura dell’insieme States.

$\begin{aligned} Function E p s i l o n C l o s u r e (⟨ Q, Σ, δ, q_{0}, F ⟩, S t a t e s) \\ N e x t S t a t e s \leftarrow \emptyset \\ ForEach q \in S t a t e s Do \\ N e x t S t a t e s \leftarrow N e x t S t a t e s \cup {q} \cup δ (q, ε) \\ EndFor \\ If N e x t S t a t e s ∖ S t a t e s = \emptyset Do \\ Return S t a t e s \\ Else \\ Return E p s i l o n C l o s u r e (⟨ Q, Σ, δ, q_{0}, F ⟩, N e x t S t a t e s) \\ EndIf \\ EndFunction \end{aligned}$

Usiamo questa funzione in quella che simula il funzionamento dell’automa non deterministico. L’ingresso è l’automa, la parola in ingresso w = w₁w₂… w_n e l’insieme di stati in cui l’automa si trova al momento. L’uscita è la risposta Sì oppure No, a seconda che l’automa accetti o non accetti la parola data.

$\begin{aligned} Function C o m p u t e N F A (⟨ Q, Σ, δ, q_{0}, F ⟩, w, S t a t e s) \\ If w = ϵ Do \\ If S t a t e s \cap F \neq \emptyset Do \\ Return YES \\ Else \\ Return NO \\ EndIf \\ EndIf \\ N e x t S t a t e s \leftarrow \emptyset \\ ForEach q \in S t a t e s Do \\ N e x t S t a t e s \leftarrow N e x t S t a t e s \cup δ (q, w_{1}) \\ EndFor \\ N e x t S t a t e s \leftarrow E p s i l o n C l o s u r e (⟨ Q, Σ, δ, q_{0}, F ⟩, N e x t S t a t e s) \\ Return C o m p u t e N F A (⟨ Q, Σ, δ, q_{0}, F ⟩, w_{2} w_{3} \dots w_{n}, N e x t S t a t e s) \\ EndFunction \end{aligned}$

Se vogliamo verificare se l’automa accetta la parola w, chiamiamo la funzione così: ComputeNFA(⟨Q, Σ, δ, q₀, F⟩, w, EpsilonClosure(⟨Q, Σ, δ, q₀, F⟩, {q₀})).

Fonti

Capitoli: Automa a stati finiti, Automa completo, Automa a stati finiti non deterministico, Simulazione di un automa non deterministico, Conversione da NFA a DFA

« Precedente: Automa a stati finiti non deterministico

Successivo: Conversione da NFA a DFA »