●
Discreto: le variabili d'ingresso, distato, d'uscita, possono assumere solo
valori discreti.
L'automa a stati finiti è un modello di calcolo semplice rappresentabile come un
piccolo dispositivo, che mediante una testina legge una stringa in 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 ASD è 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 det W&֖