Automa a stati finiti non deterministico

L’automa a stati finiti presentato nei capitoli precedenti (lo abbreviamo con DFA) era sempre deterministico, e questo si vedeva dal fatto che in ogni momento era chiaro che cosa avrebbe fatto l’automa. Ora vediamo il concetto più generale di automi a stati finiti non deterministici (li abbreviamo con NFA), in cui possono esistere transizioni che partono dallo stesso stato con lo stesso simbolo.

Esempio

Osserva il diagramma del seguente automa:

Che cosa ha di strano? Dal nodo q₀ partono due archi per il simbolo 0. Se proviamo ad accettare la parola 001, sembrerebbe che l’automa non sappia se deve restare nello stato q₀ o se deve seguire la transizione verso q₁. Un automa del genere sarebbe non deterministico.

Il determinismo in questo senso significa che in ogni situazione è chiaro che cosa farà l’automa, non c’è spazio per l’ambiguità. Un automa deterministico ha per ogni stato e per ogni simbolo una sola transizione. Il non determinismo indica ambiguità: da uno stato possono partire, per lo stesso simbolo, anche tre transizioni.

E allora come decide l’automa? L’automa non deterministico sceglie sempre (a volte diciamo anche «indovina») la transizione che porta ad accettare la parola, se è possibile.

Se diamo all’automa la parola 001, l’automa ha queste possibilità di trattarla:

$\begin{array}{r} q_{0} \to q_{0} \to q_{0} \to q_{0} \\ q_{0} \to q_{0} \to q_{1} \to q_{2} \end{array}$

più le possibilità in cui non legge l’intera parola. Nel primo ramo restava sempre nello stato q₀, cosa che può certamente fare, perché le regole di transizione lo permettono. Nel secondo ha osato andare negli altri stati e alla fine è arrivato nello stato q₂, che è finale. In questo ramo l’automa accetterebbe la parola. L’automa non deterministico sceglie automaticamente il ramo in cui accetta la parola, se un ramo del genere esiste.

Come fa a scegliere automaticamente il ramo «favorevole»? Possiamo immaginarlo così: l’automa non deterministico percorre tutti i rami possibili e, se trova un ramo in cui accetta la parola, allora accetta la parola. Come potrebbe percorrere tutti i rami? Semplicemente, nel momento in cui si trova in uno stato da cui partono n archi per il simbolo attuale, l’automa copia sé stesso n volte e ogni copia segue una strada diversa. In questo modo percorriamo via via tutte le possibilità.

Rappresentazione ad albero del calcolo dell’automa

Modifichiamo leggermente l’automa precedente:

Il non determinismo resta nel primo stato. L’automa precedente accettava tutte le parole che terminano con 01. Questo automa modificato accetta tutte le parole che contengono la sottoparola 01. Accetta quindi per esempio la parola 101 o 0101. Tutti i rami del calcolo si possono visualizzare facilmente con un albero; per esempio, per la parola 01010 l’albero potrebbe essere così:

All’inizio siamo nello stato iniziale q₀. In ingresso abbiamo la parola 01010, il primo carattere non ancora letto è 0. Dallo stato q₀ partono due transizioni per il simbolo 0, verso gli stati q₀ e q₁. L’albero avrà quindi in questo nodo due figli: q₀ e q₁. Poi leggiamo il simbolo 1. Qui non c’è alcuna ambiguità, ci spostiamo negli stati q₀ e q₂. Poi leggiamo il carattere 0; nel ramo sinistro si presenta di nuovo l’ambiguità, quindi dividiamo il calcolo in altri due rami. In uno restiamo di nuovo in q₀ e nell’altro andiamo in q₁. E così via.

Osserva che in tutto due rami terminano nello stato q₂, cioè in uno stato finale. Esistono due rami del calcolo con cui l’automa può accettare la parola data. Questo automa accetterebbe quindi la parola 01010. Possiamo provare a costruire un albero analogo per la parola 1000.

Il calcolo o resta nello stato q₀ o passa nello stato q₁, ma da lì non ha più dove andare, perché in ingresso ci sono ormai solo zeri e lo stato q₁ ha una transizione solo per il simbolo 1. Nessun ramo del calcolo termina in uno stato finale, quindi l’automa non accetta la parola 1000.

ε-transizioni

Negli automi non deterministici possiamo inoltre usare le ε-transizioni. Sono transizioni che possiamo eseguire qualunque sia il simbolo in ingresso, e senza leggere alcun simbolo della parola. Come potremmo scrivere un automa non deterministico che accetti la parola vuota, tutte le parole composte solo da uni e le parole della forma (10)ⁿ, cioè 10, 1010, …?

Abbiamo diviso l’automa in due «sottoautomi». Quello superiore si occupa di riconoscere le parole composte da 1, quello inferiore si occupa delle parole della forma (10)ⁿ. Proviamo ad accettare la parola 111. All’inizio l’automa si trova nello stato q₀ e in ingresso ha la parola 111. Poiché ha a disposizione le ε-transizioni, può decidere di passare nello stato q₁ o q₂, a seconda di come gli conviene. Vediamo che gli converrà passare nello stato q₁. L’automa ci passa. E in ingresso ha ancora la parola 111! Solo a questo punto comincia a leggere i simboli della parola e a passare dallo stato q₁ di nuovo in q₁, finché legge l’intera parola e la accetta.

Se provassimo ad accettare 1010, all’inizio l’automa passerebbe nello stato q₂ e solo da lì comincerebbe a elaborare i simboli e accetterebbe di nuovo la parola.

Per la parola 1100 l’automa potrebbe fare qualsiasi cosa, non ha modo di accettare una parola del genere.

Le ε-transizioni e il non determinismo ci semplificano il lavoro in molti casi; per esempio, la dimostrazione che l’unione di linguaggi regolari è ancora un linguaggio regolare si scrive con le ε-transizioni in modo molto più semplice che nel caso degli automi a stati finiti deterministici. In quella dimostrazione avevamo esempi di questi automi

e poi avevamo costruito un automa a stati finiti deterministico che accettava l’unione dei due linguaggi. Con le ε-transizioni possiamo costruire un automa del genere così:

Basta aggiungere un nuovo stato iniziale, da cui partono due ε-transizioni verso gli stati iniziali degli automi originali, e il gioco è fatto. L’automa decide in modo non deterministico se provare ad accettare la parola con l’uno o con l’altro «sottoautoma».

Definizione di automa non deterministico

Abbiamo già mostrato in che cosa differiscono l’automa a stati finiti deterministico e quello non deterministico, resta solo da formalizzarlo. L’automa a stati finiti deterministico lo abbiamo definito come una quintupla ⟨Q, Σ, δ, q₀, F⟩, dove Q è l’insieme degli stati, Σ è l’alfabeto, δ è la funzione di transizione, q₀ è lo stato iniziale e F è l’insieme degli stati finali. L’unica cosa che cambia nella definizione degli automi non deterministici è la definizione della funzione di transizione.

Nella versione deterministica la funzione per la chiamata δ(q, w) poteva restituire un solo stato, mentre nella versione non deterministica può restituire più stati – se per un simbolo sono definite più transizioni. Poiché dobbiamo definire anche le ε-transizioni, indichiamo l’insieme Σ ∪ {ε} con Σ_ε, cioè Σ_ε = Σ ∪ {ε}. La funzione δ la definiamo quindi come

$δ : Q \times Σ_{ε} \to 2^{Q}$

Con 2^Q indichiamo l’insieme delle parti, l’insieme di tutti i sottoinsiemi dell’insieme Q. La formalizzazione del calcolo è molto simile a quella degli automi a stati finiti. La configurazione dell’automa è di nuovo una coppia ⟨q, w⟩ ∈ Q × Σ^∗. Il passo di calcolo ↦ è una relazione sull’insieme delle configurazioni tale che

$⟨ q_{i}, w_{0} w_{1} \dots w_{n} ⟩ \mapsto ⟨ q_{j}, w_{1} \dots w_{n} ⟩,$

se e solo se q_j ∈ δ(q_i, w₀). In questa frase c’era la differenza più grande. Negli automi deterministici avevamo scritto questa condizione come q_j = δ(q_i, w₀), perché la funzione δ restituiva sempre un solo stato. La versione non deterministica della funzione di transizione restituisce un insieme di stati, perciò c’è il simbolo ∈. La chiusura riflessiva e transitiva della relazione la indicheremo di nuovo con ↦ ^∗. Diciamo che l’automa accetta la parola w se e solo se esiste q_f ∈ F tale che

$⟨ q_{0}, w ⟩ \mapsto^{*} ⟨ q_{f}, ε ⟩ .$

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 completo

Successivo: Simulazione di un automa non deterministico »