Automa a Stati Finiti

Questa applicazione implementa un algoritmo per ridurre un Automa a Stati Finiti.

Un automa a stati finiti (ASF) o macchina a stati finiti o FSA (dall'inglese Finite State Automata) è un modello che permette di descrivere con precisione e in maniera formale il comportamento di molti sistemi. Grazie alla sua semplicità e chiarezza questo tipo di modello è molto diffuso nell'ingegneria e nelle scienze, soprattutto nel campo dell'informatica e della ricerca operativa. Un automa a stati finiti può essere utilizzato sia per modellare un sistema esistente che per modellare un nuovo sistema formale in grado di risolvere alcuni problemi esistenti. A quest'ultima categoria appartengono i cosiddetti riconoscitori di linguaggi e i traduttori. La rappresentazione grafica di un automa a stati finiti è il grafo.

Nello specifico, con gli automi a stati finiti, si possono modellare tutti i sistemi che possiedono le seguenti caratteristiche:

Dinamicità: caratteristica di evolvere nel tempo passando da uno stato ad un altro.

Discretezza: caratteristica che indica che le variabili d'ingresso e gli stati del sistema da modellare possono essere espressi con valori discreti.

Simboli finiti: caratteristica che determina che il numero di simboli di ingresso e di stati sia rappresentabile da un numero finito.

Dal punto di vista pratico, il concetto di automa a stati finiti equivale a costruire un piccolo dispositivo che mediante una testina legge una stringa di input su un nastro e la elabora, facendo uso di un meccanismo molto semplice di calcolo e di una memoria limitata. L'esame della stringa avviene un carattere alla volta attraverso precisi passi computazionali che comportano l'avanzamento della testina. In sostanza un ASF è un caso particolare di macchina di Turing, utilizzato per l'elaborazione di quei linguaggi che nelle Grammatiche di Chomsky sono definiti di Tipo 3 o Regolari. Distinguiamo due tipi di automi a stati finiti: gli automi a stati finiti deterministici (ASFD) e gli automi a stati finiti non deterministici ASFND che si contraddistinguono per la loro differente potenza espressiva.