Un automa a stati finiti (Finite State Automata) o macchina a stati finiti (Finite State Machine) è in generale un dispositivo che in ogni istante può trovarsi in uno fra un numero finito di stati. La transizione da uno stato a quello successivo dipende dallo stato di partenza e dagli eventuali ingressi applicati all'automa. Inoltre l'automa può produrre dei valori di uscita che dipendono dallo stato corrente, ma in generale non coincidono con esso.
Per quanto riguarda in particolare le uscite, esse possono dipendere solo dallo stato (come in tutti gli esempi visti finora) e allora si parla di automa di Moore. Lo schema generale di un automa di Moore è mostrato in figura:
E' anche possibile progettare automi in cui le uscite dipendono sia dallo stato che dagli ingressi. Queste macchine sono dette automi di Mealy e il loro schema generale è il seguente:
Nel seguito non tratteremo ulteriormente gli automi di Mealy, anche se è possibile dimostrare che non esistono automi che non si possano realizzare in entrambi i modi (sia con una macchina di Moore che con una di Mealy), anche se la complessità delle due soluzioni non è sempre identica (spesso gli automi di Moore richiedono un numero maggiore di stati).
Gli automi si distinguono poi in sincroni (quando la transizione fra stati viene comandata da un clock esterno) oppure asincroni (quando non c'è segnale di clock).
Gli automi a stati finiti sono una tipologia di modello usato in molte discipline diverse, fra cui la linguistica, la biologia, la matematica e la logica. In informatica gli automi sono usati per il progetto di sistemi digitali, compilatori, protocolli di rete e riconoscimento di linguaggi.
E' facile vedere come questa definizione comprenda tutti i contatori visti nelle lezioni precedenti. Anzi, in generale qualsiasi contatore può essere pensato come un automa a stati.
Ma anche i semplici FF sono automi a stati. Per esempio il diagramma degli stati di un FF JK è il seguente:
Nonostante la semplicità del dispositivo, il diagramma degli stati non è banale e merita qualche spiegazione. Si noti anzitutto il fatto che gli stati sono solo due e corrispondono ai valori 0 e 1 dell'uscita Q (l'altra uscita Q è sempre complementare a Q e dunque non aumenta il numero degli stati possibili).
Si osservi inoltre come fra i due stati sono possibili più transizioni. Per esempio si passa dallo stato 1 allo stato 0 in presenza di un "reset" (J = 0 e K = 1) oppure in presenza di un comando di "toggle" (J = 1 e K = 1). Notiamo infine che in presenza degli ingressi J = 0 e K = 0 lo stato successivo è uguale allo stato precedente, come mostra l'arco di transizione che nel nostro diagramma si richiude sullo stato stesso.
Un altro classico esempio di automa è una macchina distributrice di bevande, per esempio di caffè. Supponiamo che il costo del caffè sia 15 centesimi di euro e che la macchina possa accettare monete da 5 oppure 10 centesimi (si tratta ovviamente di prezzi irrealistici, ma questo non ha nessuna importanza per noi).
Il diagrammi degli stati in questo caso è mostrato in figura:
Gli stati sono indicati in base al valore delle monete inserite fino a quel momento (es. 10 indica che sono stati inseriti 10 centesimi). Come abbiamo già avuto modo di notare, la corrispondenza fra gli stati e una particolare combinazione binaria è arbitraria, per cui potremmo poi numerare i cinque stati a piacere (000, 001, 010, 011 e 101).
I valori indicati accanto alle frecce delle transizioni rappresentano la moneta aggiunta in ingresso al distributore. Lo stato iniziale (0) rappresenta la condizione in cui la macchina è stata appena accesa e non sono state ancora inserite monete. Le uscite possibili sono caffè (in corrispondenza dello stato 15) e caffè + resto (in corrispondenza dello stato 20).
Volendo essere rigorosi, bisognerebbe anche aggiungere delle transizioni di alcuni stati su se stessi, nel caso in cui non vengano aggiunte monete (per esempio nello stato 10 se non vengono aggiunte monete, si ritorna ciclicamente allo stato 10).
Sito realizzato in base al template offerto da
http://www.graphixmania.it
