Automi a stati finiti

Un automa a stati finiti o macchina a stati finiti (Finite State Machine, FSM) è un modello matematico di un sistema che può esistere in uno stato tra un insieme finito di stati possibili.

È particolarmente utile per rappresentare e gestire sistemi computazionali con comportamenti discreti e con un numero finito di stati distinti, come i protocolli di comunicazione, i circuiti digitali e i software di controllo.

Un automa a stati finiti è costituito dai cinque elementi:

1. Stati: Un insieme finito di stati, uno dei quali è designato come stato iniziale. E' generalmente indicato con la lettera $ Q $
2. Alfabeto di input: Un insieme finito di simboli che l'automa può leggere come input. E' noto come alfabeto ed è indicato con la lettera greca maiuscola $ \Sigma $.
3. Funzione di transizione: Una funzione che mappa ogni coppia di uno stato e un simbolo di input in un nuovo stato. $$ \delta: Q \times \Sigma \rightarrow Q $$ In altre parole indica i simboli che determinano le varie azioni in ogni singolo stato.
4. Stato iniziale: Lo stato in cui l'automa si trova all'inizio. E' un elemento dell'insieme degli stati $ q_0 \in Q $.
5. Stati finali: Un sottoinsieme di stati che sono considerati stati di accettazione o di conclusione. Lo indichiamo con la lettera $ F $ E' un sottoinsieme dell'insieme degli stati $ F \subseteq Q $.

Pertanto, un automa finito è formalmente definito come una 5-upla detta descrizione formale.

$$ (Q, \Sigma, \delta, q_0, F ) $$

L'automa finito legge una stringa di input $ w  $ da sinistra verso destra, simbolo per simbolo, passando da uno stato all'altro secondo la funzione di transizione \(\delta\).

In alternativa alla descrizione formale l'automa può essere rappresentato anche tramite un diagramma di stato.

Ogni passaggio da uno stato a un altro è detto transizione e può essere rappresentato anche tramite una tabella detta tabella delle transizioni.

$$
\begin{array}{c|cc}
 & 0 & 1 \\
\hline
q_0 & q_1 & q_0 \\
q_1 & q_1 & q_2 \\
q_2 & q_1 & q_0 \\
\end{array}
$$

Il processo inizia nello stato iniziale \(q_0\) e continua fino a esaurire i simboli della stringa.

Se, al termine della stringa, l'automa si trova in uno stato di accettazione \(F\), la stringa è accettata; altrimenti, è rifiutata.

In conclusione, a seconda delle stringhe l'output dell'automa può essere "accetta" o "rifiuta".

Le applicazioni pratiche. Gli automi a stati finiti trovano applicazione in molte aree, tra cui l'analisi del linguaggio, per il riconoscimento di pattern e la validazione di stringhe secondo specifiche regole sintattiche. Sono utilizzati anche nella progettazione dei circuiti digitali, come nei sistemi di controllo discreti (es. controller degli ascensori e dei semafori) e nei protocolli di comunicazione per gestire la sequenza di eventi nelle reti di comunicazione. Sono impiegati nella fase di analisi lessicale dei compilatori dei linguaggi di programmazione per riconoscere i token nel codice sorgente.

Gli automi finiti rappresentano un concetto chiave nella teoria della computazione e nella teoria dei linguaggi formale, trovano applicazione in molte aree pratiche dell'informatica e dell'ingegneria.

La loro capacità di modellare i comportamenti sequenziali e analizzare sistemi sequenziali con un numero finito di stati li rende strumenti utili per comprendere e progettare sistemi complessi.

Esempio di automa a stati finiti

Consideriamo un automa finito deterministico \( M \) che riconosce stringhe binarie che terminano con "01". Se la stringa è riconosciuta, l'automa compie un'azione particolare, ad esempio apre una porta. Questo automa è definito come segue:

• Stati: \( Q = \{q_0, q_1, q_2\} \)
• Alfabeto di input: \( \Sigma = \{0, 1\} \)
• Funzione di transizione \( \delta \):
  - \(\delta(q_0, 0) = q_1\)
  - \(\delta(q_0, 1) = q_0\)
  - \(\delta(q_1, 0) = q_1\)
  - \(\delta(q_1, 1) = q_2\)
  - \(\delta(q_2, 0) = q_1\)
  - \(\delta(q_2, 1) = q_0\)
• Stato iniziale: \( q_0 \)
• Stato di accettazione: \( F = \{q_2\} \)

Questo automa parte dallo stato \( q_0 \). Se legge "0" quando si trova nello stato iniziale, passa a \( q_1 \). Se legge "1" nello stato \( q_1 \), passa a \( q_2 \). Se termina in \( q_2 \) dopo aver letto l'input, l'input è accettato.

Il funzionamento di questo automa è rappresentato graficamente con questo diagramma degli stati.

Di solito, gli stati di accettazione nell'insieme \( F \) sono rappresentati con un doppio cerchio, mentre lo stato iniziale è indicato da una freccia che punta verso di esso senza provenire da altri stati.

In questo esempio, l'automa accetta stringhe binarie che terminano con "01".

La tabella delle transizioni dell'automa è la seguente:

$$
\begin{array}{c|cc}
 & 0 & 1 \\
\hline
q_0 & q_1 & q_0 \\
q_1 & q_1 & q_2 \\
q_2 & q_1 & q_0 \\
\end{array}
$$

A seconda della stringa in input l'automa ha un comportamento (output) diverso. Può accettare o rifiutare la stringa.

Vediamo un esempio pratico con la stringa w = "101":

1. La macchina si trova nello stato iniziale \( q_0 \) ed elabora il primo carattere "1", restando nello stesso stato \( q_0 \).
   
2. Elabora il secondo carattere "0" e passa allo stato \( q_1 \).
   
3. Elabora il terzo e ultimo carattere "1" e passa allo stato \( q_2 \).
   
4. La stringa è terminata e la macchina è nello stato \( q_2 \). Poiché \( q_2 \) è uno stato di accettazione, la macchina accetta la stringa w="101".

Ora vediamo cosa accade con la stringa w = "010":

1. La macchina si trova nello stato iniziale \( q_0 \) ed elabora il primo carattere "0", passando allo stato \( q_1 \).
   
2. Elabora il secondo carattere "1" e passa allo stato \( q_2 \).
   
3. Elabora il terzo e ultimo carattere "0" e passa allo stato \( q_1 \).
   
4. La stringa è terminata e la macchina è nello stato \( q_1 \). Poiché \( q_1 \) non è uno stato di accettazione, la macchina rifiuta la stringa.

In questo esempio abbiamo analizzato cosa accade quando la macchina legge due stringhe, w="101" e w="010", la macchina accetta la prima e rifiuta la seconda.

L'insieme di tutte le stringhe accettate dalla macchina forma un insieme particolare detto linguaggio della macchina, \( L(M) \).

Il linguaggio della macchina è l'insieme delle stringhe accettate dalla macchina.

Linguaggio della macchina

Il linguaggio di una macchina a stati finiti, denotato come \(L(M)\), è l'insieme di tutte le stringhe di input che l'automa finito \(M\) accetta.

Formalmente, \(L(M)\) è definito come segue:

\[ L(M) = \{ w \in \Sigma^* \mid M \text{ accetta } w \} \]

Dove \(\Sigma^*\) rappresenta l'insieme di tutte le stringhe finite che possono essere formate con l'alfabeto \(\Sigma\).

Una stringa \(w\) è accettata da \(M\) se, partendo dallo stato iniziale e processando tutti i simboli di \(w\) secondo la funzione di transizione \(\delta\), l'automa termina in uno stato di accettazione.

Un linguaggio è detto linguaggio regolare se esiste qualche automa finito in grado di riconoscerlo.

Esempio di linguaggio della macchina

Consideriamo nuovamente l'automa finito deterministico \(M\) che riconosce stringhe binarie che terminano con "01".

Il linguaggio \(L(M)\) della macchina \(M\) è l'insieme di tutte le stringhe binarie che terminano con "01".

Alcuni esempi di stringhe accettate da \(M\) sono:

- "01"
- "101"
- "00001"
- "111101"

Formalmente, possiamo descrivere il linguaggio \(L(M)\) di questa macchina come:

\[ L(M) = \{ w \in \{0, 1\}^* \mid w \text{ termina con "01"} \} \]

In altre parole, \(L(M)\) include tutte le stringhe binarie che hanno "01" come ultimi due simboli.

Qualsiasi stringa binaria che non termina con "01" non sarà accettata dall'automa \(M\).

Tipi di automi finiti

In generale un automa a stati finiti (ASF) è un modello computazionale utilizzato per rappresentare e analizzare il comportamento di sistemi discreti.

Esistono due tipi principali di automi a stati finiti: deterministici e non deterministici.

• Automi a stati finiti deterministici (DFA)
  In un DFA, per ogni stato e simbolo di input, la funzione di transizione \(\delta\) specifica esattamente un unico stato successivo. Questo rende il comportamento dell'automa completamente prevedibile e deterministico.
• Automi a stati finiti non deterministici (NFA)
  In un NFA, la funzione di transizione \(\delta\) può specificare più stati successivi per un dato stato e simbolo di input, o anche nessuno stato successivo. Questo introduce una componente di non determinismo, dove l'automa può seguire diversi percorsi di esecuzione simultaneamente.
• Automi a stati finiti con transizioni epsilon (ε-NFA)
  Un ε-NFA è un'estensione dell'NFA che consente transizioni "epsilon", che sono transizioni che l'automa può effettuare senza consumare alcun simbolo di input. Queste transizioni consentono una maggiore flessibilità nella definizione dei comportamenti dell'automa.