Gli Automi a Stati Finiti

Riprendiamo l’argomento dei linguaggi formali per introdurre uno strumento estremamente potente, preziosissimo per la nostra borsa del matematico: gli automi a stati finiti.

Nel post dedicato ai grafi abbiamo visto come un grafo sia costituito da un insieme di nodi e di archi. Entreremo nel dettaglio della descrizione formale in un post successivo, concentrandoci ora esclusivamente sugli aspetti essenziali. Un automa a stati finiti è rappresentabile mediante un grafo orientato dove ciascun nodo corrisponde ad uno stato del sistema ed ogni arco rappresenta un passaggio tra stati. L’automa ha uno stato iniziale ed uno finale, rappresentati da una freccia entrante (stato iniziale) e da un doppio circoletto (stato finale).

Non volendo ricorrere alla notazione matematica, un automa a stati finiti può essere descritto unicamente mediante il grafo orientato detto diagramma di transizione. L’automa è uno strumento potentissimo per rappresentare le evoluzioni di un sistema che cambia nel tempo sulla base di un insieme di stati finito. L’idea alla base di un automa a stati finiti è quella di rappresentare l’evoluzione del sistema che passa da uno stato all’altro in risposta ad eventi specifici, rappresentati da archi uscenti ed entranti.

L’automa è detto deterministico se ad ogni stato è associato un solo arco uscente a rappresentare lo stesso evento. Sotto queste condizioni, l’automa è detto invariante perché il risultato fornito, cioé lo stato in cui si trova l’automa, è sempre lo stesso a parità della sequenza di eventi in ingresso. Grafi ed algoritmi (ricordate ?) sono parenti molto stretti, anche se il terreno d’elezione dei grafi è nel riconoscimento dei linguaggi formali. Associando un simbolo ad ogni arco, possiamo costruire un automa che riconosce stringhe costruite in modo opportuno.

L’automa seguente riconosce, ad esempio, tutte e sole le stringhe composte da un numero pari di 1 e 0, alternati:

ad esempio 10, 1010, 101010 sono tutte strighe riconosciute perché dandole in ingresso all’automa, a partire dallo stato iniziale q0, lo fanno arrestare nello stesso stato, che è anche finale. La stringa 101 non è riconosciuta dall’automa perché lo fa arrestare al passo q1, che non è finale.

Questo automa è un po’ più sofisticato:

e riconosce tutte e sole le stringhe costituite da un numero pari di 0 e da un numero pari di 1, come ad esempio 1001, 10100011.

In post successivi, prima di dare la definizione formale degli automi a stati finiti, vedremo uno strumento fondamentale per la teoria dei linguaggi formali: le espressioni regolari.