Automa a stati finiti

Un automa a stati finiti (in inglese finite state machine o finite automaton) è un modello di calcolo di un computer primitivo, composto da alcuni stati e da alcune transizioni, che è in grado di accettare o rifiutare una parola data.

Esempio

Descriviamo in modo informale un automa a stati finiti con un diagramma degli stati:

L’automa è formato da stati; nella figura sono i tre stati rotondi q₀, q₁ e q₂. Tra questi stati ci sono le transizioni, cioè le frecce. Nell’automa deve inoltre esserci uno stato iniziale, che è lo stato q₀. Lo stato iniziale si disegna spesso con una freccia che entra in esso e non parte da nessuno stato. Di solito nell’automa c’è anche uno stato finale, che disegniamo con una doppia linea, quindi nella figura è lo stato q₂.

Un automa costruito così accetta certe parole. Diamo all’automa delle parole e l’automa prova ad accettarle. Se le accetta, risponde SÌ, se non le accetta, risponde NO. Il nostro automa prova ad accettare parole composte dalle lettere «a, b, c», quindi possiamo provare con la parola «abbc».

Partiamo dallo stato iniziale q₀ e in ingresso abbiamo la parola «abbc». Poi seguiamo le frecce.

Percorriamo la parola nel modo consueto, da sinistra a destra, quindi per primo prendiamo il simbolo «a». La freccia per l’ingresso «a» va nello stato q₁, quindi ci passiamo e togliamo il simbolo «a» dalla parola. In ingresso abbiamo la parola «bbc»:

La freccia per l’ingresso «b» torna indietro al nodo q₁. Togliamo di nuovo la prima lettera e in ingresso abbiamo la parola «bc». Restiamo di nuovo nello stato q₁. Alla fine in ingresso abbiamo la parola «c». Dallo stato q₁ la freccia per l’ingresso «c» ci manda nello stato q₂.

Abbiamo esaurito tutte le lettere della parola di ingresso e siamo nello stato q₂, che è uno stato finale. Questo automa a stati finiti accetta quindi la parola «abbc».

Se alla fine non fossimo in uno stato di accettazione, l’automa non accetterebbe la parola. Allo stesso modo l’automa non accetterebbe la parola se in qualche stato non avessimo dove andare. Per esempio, con l’ingresso «ab» arriveremmo nello stato q₁ e lì ci fermeremmo – l’automa non accetta una parola del genere. Se provassimo la parola «aabbc», saremmo di nuovo sfortunati, perché dallo stato q₁ non parte nessuna freccia per la lettera «a».

L’automa a stati finiti serve quindi a riconoscere un certo insieme di parole. In pratica potremmo usare un automa, per esempio, per verificare se la parola in ingresso è un indirizzo email valido.

Definizione di automa a stati finiti

L’idea intuitiva di che cos’è un automa a stati finiti va formalizzata, per poter lavorare con gli automi più a fondo e meglio.

Diciamo che un automa a stati finiti (deterministico) è una quintupla ⟨Q, Σ, δ, q₀, F⟩, dove

• Q è un insieme finito di stati,
• Σ (sigma maiuscola) è l’alfabeto (un insieme finito di simboli/lettere),
• δ: Q × Σ ⟶ Q è la funzione di transizione,
• q₀ ∈ Q è lo stato iniziale,
• F ⊆ Q è l’insieme degli stati finali (di accettazione).

Torniamo all’automa precedente,

e possiamo dire che nell’insieme degli stati Q ci sono tre stati Q = {q₀, q₁, q₂}. L’alfabeto Σ contiene le lettere con cui possiamo formare le parole che l’automa accetterà o rifiuterà. Qui probabilmente è l’alfabeto Σ= {a, b, c}, ma può essere anche un qualsiasi sovrainsieme. Lo stato iniziale q₀ è lo stato q₀, qui non cambia nulla. L’insieme degli stati finali ha in questo automa un solo stato F = {q₂}.

Per funzione di transizione intendiamo queste tre frecce con le lettere. Se la notazione δ: Q × Σ ⟶ Q ti confonde, significa solo che δ è una funzione (o forse meglio un’applicazione) che prende due parametri: uno stato di Q e una lettera di Σ. Quando la chiamiamo, restituisce un nuovo stato. La nostra funzione di transizione potremmo definirla con una tabella così:

$$\begin{array}{ccc}Q& \mathrm{\Sigma }& \to Q\\ q_0& a& q_1\\ q_1& b& q_1\\ q_1& c& q_2\end{array}$$

Se quindi chiamiamo δ(q₁, c), applichiamo la terza riga e la funzione risponde con lo stato q₂ – proprio come il diagramma. Se siamo nello stato q₁ e in ingresso c’è la lettera «c», arriviamo nello stato q₂. Prima di definire formalmente che cosa significa che un automa accetta una parola, ci affidiamo alla comprensione intuitiva di questo concetto e vediamo altri esempi.

Altri esempi

1. Costruisci un automa che lavora sull’alfabeto binario, cioè Σ= {0, 1}, e accetta soltanto le parole che terminano con un 1. Per esempio accetta le parole 1, 01, 000001, 0101011.

   

   Il nostro automa ha due stati: quello iniziale q₀ e quello finale q₁. Ogni volta che in ingresso c’è la cifra 1, passiamo nello stato finale q₁ e ci restiamo. Invece, se in ingresso c’è la cifra 0, passiamo nello stato non finale q₀ e restiamo anche lì.

2. Costruisci un automa sull’alfabeto binario che accetta soltanto le parole la cui lettera iniziale è diversa dalla lettera finale.

   

   Già nel primo passo l’automa si divide in due «sottoautomi». Se la parola inizia con 0, l’automa entra nella parte sinistra e ci resta, se inizia con 1, passa alla parte destra. Poi è la solita storia: se siamo nella parte sinistra e in ingresso c’è 1, passiamo nello stato finale e ci restiamo. Se in ingresso c’è 0, passiamo nello stato q₁, che non è finale.

   A differenza degli automi precedenti, questo automa ha più stati finali, cioè F = {q₃, q₄}.

3. Costruisci un automa sull’alfabeto binario che accetta soltanto le parole che non contengono due zeri consecutivi.

   

   Questo automa è interessante per due motivi: il primo è che accetta la parola vuota. Possiamo provare a dare all’automa la parola vuota e l’automa la accetta se lo stato iniziale è anche uno stato finale, come accade in questo automa. Poiché la parola vuota è una parola che non contiene due zeri consecutivi, è proprio quello che ci aspettiamo. L’altra particolarità è che in questo automa tutti gli stati sono finali. L’unico caso in cui l’automa non accetterebbe una parola è quando da uno stato non partisse nessuna transizione. Succede nello stato q₁, che non ha una transizione per 0, perché altrimenti la parola conterrebbe due zeri consecutivi.

4. Costruisci un automa sull’alfabeto {-,+,.,0,1,…,9} che accetta soltanto le parole che rappresentano un numero. Cioè o un numero intero come 2, 548, 98263, oppure un numero decimale come 5584.48, 3.14, ed entrambi anche nella versione per i numeri negativi con il segno meno -2, -548, -3.14 e anche con il segno più scritto esplicitamente, cioè +2, +548, +3.14. Inoltre dobbiamo essere in grado di scrivere il numero 0.123 anche solo come .123 (senza lo zero iniziale), e questo con entrambi i segni. Introduciamo una notazione ausiliaria: invece di scrivere dieci transizioni per le dieci cifre, useremo il simbolo N.

   

5. Costruisci un automa sull’alfabeto binario che accetta soltanto le parole della forma 0ⁿ1ⁿ, cioè parole che all’inizio hanno un certo numero di zeri, seguiti dallo stesso numero di uni. Esempi di tali parole sono 0011, 00001111, 01.

   Un automa del genere non si può costruire, perché non siamo in grado di «ricordare» da nessuna parte il numero di zeri. Dovremmo creare diversi «sottoautomi», come nel secondo esempio, ma questi «sottoautomi» dovrebbero essere infiniti, uno per ogni valore di n.

Formalizzazione del calcolo dell’automa

Abbiamo già definito formalmente l’automa a stati finiti. Dobbiamo ancora definire che cosa fa un automa di questo tipo, cioè definire il calcolo dell’automa.

Configurazione dell’automa: diciamo che una coppia ⟨q, w⟩ ∈ Q × Σ^∗ è una configurazione dell’automa, dove q è lo stato attuale in cui si trova l’automa e w è la parte della parola non ancora letta. Σ^∗ indica la chiusura dell’alfabeto Σ, l’insieme di tutte le parole che si possono formare con le lettere dell’alfabeto Σ. Della chiusura fa parte anche la parola vuota, che indichiamo con ε.

Dato un automa ⟨Q, Σ, δ, q₀, F⟩, se cerchiamo di accettare la parola w, l’automa si trova nella configurazione iniziale ⟨q₀, w⟩. Se torniamo all’automa

e vogliamo accettare la parola w = abbc, la configurazione iniziale sarà ⟨q₀, abbc⟩.

Il passo di calcolo lo definiamo come una relazione ↦ tra gli insiemi (Q × Σ^∗) × (Q × Σ^∗), cioè tra le configurazioni dell’automa. Sia w = w₀w₁… w_n la parte non ancora letta della parola w. Allora diciamo che le coppie ⟨q₁, w₀w₁… w_n⟩ e ⟨q₂, w₁… w_n⟩ sono nella relazione ↦, e scriviamo

$$⟨q_1,w_0{w}_1\dots w_n⟩\mapsto ⟨q_2,w_1\dots w_n⟩,$$

se e solo se δ(q₁, w₀) = q₂. Tornando al nostro esempio, la configurazione iniziale è ⟨q₀, abbc⟩. Dal diagramma vediamo che per l’ingresso «a» possiamo spostarci nello stato q₁. Possiamo quindi scrivere

$$⟨q_0,abbc⟩\mapsto ⟨q_1,bbc⟩,$$

perché vale δ(q₀, a) = q₁. Abbiamo così eseguito un passo di calcolo: abbiamo guardato in quale stato dovremmo andare per l’ingresso dato (= la prima lettera della parte non ancora letta della parola), ci siamo andati e abbiamo tolto la prima lettera dalla parte non ancora letta della parola. Così abbiamo ottenuto una nuova configurazione.

La chiusura riflessiva e transitiva della relazione passo di calcolo si indica con ↦ ^∗. Se quindi scriviamo K₁ ↦ ^∗ K₂, dove K₁, K₂ sono configurazioni dell’automa, significa che dalla configurazione K₁ riusciamo ad arrivare alla configurazione K₂ con alcuni passi di calcolo, cioè esiste una successione finita di configurazioni tale che:

$$K_1\mapsto K_{11}\mapsto K_{12}\mapsto K_{13}\mapsto \cdots \mapsto K_2$$

Per esempio, nel nostro automa vale ⟨q₀, abbc⟩ ↦ ^∗ ⟨q₁,bc⟩, perché se eseguiamo due passi di calcolo ci resta la parola «bc» e restiamo nello stato q₁. Esiste cioè questa successione di configurazioni:

$$⟨q_0,abbc⟩\mapsto ⟨q_1,bbc⟩\mapsto ⟨q_1,bc⟩$$

L’automa accetta la parola w se e solo se esiste q_f ∈ F tale che $$⟨q_0,w⟩{\mapsto }^{\ast }⟨q_f,\epsilon ⟩$$ Questo significa che l’automa accetta la parola w se e solo se esiste una successione di passi di calcolo tale che alla fine di questa successione abbiamo letto l’intera parola e ci troviamo in uno stato finale dell’automa. Il fatto che abbiamo letto l’intera parola è espresso dal fatto che nella configurazione al posto della parola c’è ε, cioè la parola vuota. Il nostro automa accetta la parola abbc, perché esiste questa successione di configurazioni:

$$⟨q_0,abbc⟩\mapsto ⟨q_1,bbc⟩\mapsto ⟨q_1,bc⟩\mapsto ⟨q_1,c⟩\mapsto ⟨q_2,\epsilon ⟩$$

e lo stato q₂ è uno stato finale, q₂ ∈ F.

Il linguaggio accettato dall’automa è l’insieme di tutte le parole che l’automa accetta. Il linguaggio dell’automa A lo indichiamo con L(A). Vale quindi L(A) ⊆ Σ^∗ e

$$L(A)=\{w\in {\mathrm{\Sigma }}^{\ast }\mid A\text{ accetta la parola }w\}$$

Un linguaggio regolare è un linguaggio che è accettato da un qualche automa a stati finiti.

Due automi a stati finiti sono equivalenti se accettano lo stesso linguaggio. Cioè gli automi A₁ e A₂ sono equivalenti se vale L(A₁) = L(A₂).

Fonti

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