Tabella di transizione di stato

Nella teoria degli automi e dei circuiti sequenziali, una tabella di transizione di stato o tabella di stato è una tabella che mostra verso quale stato (o stati, negli automi a stati finiti non deterministici) si muoverà l'automa a numero di stati finito, in base al suo stato attuale e in base agli altri input. Una tabella di stato è essenzialmente una tabella di verità nella quale si hanno come input anche lo stato attuale e come output anche lo stato successivo.

Una tabella degli stati è uno dei modi in cui si può specificare il comportamento di un automa a numero di stati finiti. Altri modi per farlo sono: il diagramma di stato e l'equazione caratteristica.

Possibili forme

Tabella di stato ad una dimensione

Le tabelle di stato di questo tipo sono chiamate anche "tabelle caratteristiche", sono tabelle di stato monodimensionali e sono molto più simili ad una tabella di verità che alla versione bidimensionale delle tabelle di stato. Gli input sono usualmente posti a sinistra, separati dagli output, che sono sulla destra. Gli output rappresentano lo stato successivo della macchina. Un semplice esempio di una macchina a stati con due stati e due input è il seguente:

A	B	Stato attuale	Stato successivo	Output
0	0	S1	S2	1
0	0	S2	S1	0
0	1	S1	S2	0
0	1	S2	S2	1
1	0	S1	S1	1
1	0	S2	S1	1
1	1	S1	S1	1
1	1	S2	S2	0

S₁ e S₂ sono comunemente rappresentati con dei singoli bit (0 e 1), dato che un singolo bit può avere solo due stati.

Tabella di stato a due dimensioni

Le tabelle di transizione di stato sono tipicamente tabelle bidimensionali. Ci sono due forme comuni per queste tabelle:

• Una delle dimensioni indica lo stato attuale, mentre l'altra dimensione indica gli eventi. Le intersezioni tra righe e colonne indicano lo stato successivo di un evento, e (opzionalmente) un'azione associata con la transizione di stato.

Tabella di transizione dello stato

Stato\Evento	E1	E2	...	En
S1	—	Sy / Aj	...	—
S2	—	—	...	Sx / Ai
...	...	...	...	...
Sm	Sz / Ak	—	...	—

(S: stato, E: evento, A: azione, —: transizione non ammessa)

• Una delle dimensioni indica lo stato attuali (o gli stati), mentre l'altra dimensione indica lo stato successivo (o gli stati). L'intersezione tra righe e colonne indica l'evento che porta ad un particolare stato successivo.

Tabella di transizione di stato

Stato attuale\Stato successivo	S1	S2	...	Sm
S1	—	—	...	Ex / Ai
S2	Ey / Aj	—	...	—
...	...	...	...	...
Sm	—	Ez / Ak	...	—

(S: stato, E: evento, A: azione, —: transizione non ammessa)

Ulteriori forme di rappresentazione

Nella macchine a numero di stati finiti multipli con transizioni simultanee, può essere mostrato cosa sia effettivamente una tabella di transizione di stato n-dimensionale, in cui gruppi di righe mappano gruppi di stati attuali verso gli stati successivi. Questa è un modo alternativo per rappresentare una comunicazione tra macchine a stati separate e interdipendenti.

All'altro estremo, diverse tabelle separate sono state usate per ogni transizione entro una singola macchina a stati: le tabelle AND/OR sono simili a tabelle di decisioni incomplete nelle quali la decisione è implicitamente anche l'attivazione della transizione associata.

Esempio

Un esempio di tabella di transizione di stato per una macchina M e del corrispondente diagramma di stato è il seguente:

Tabella di transizione di stato Stato\Input 1 0 S1 S1 S2 S2 S2 S1

Diagramma di stato

Tutti i possibili input in ingresso alla macchina sono nelle colonne della tabella. Tutti i possibili stati sono nelle righe. È possibile vedere che se la macchina è nello stato S₁ (la prima riga), e l'input successivo è il carattere 1, allora la macchina rimarrà nello stato S₁. Se l'input è un carattere 0, la macchina eseguirà una transizione verso lo stato S₂, come può essere visto nella seconda colonna. Nel diagramma, lo stesso comportamento può essere osservato con la freccia diretta da S₁ verso S₂, etichettata con un carattere 0. Questo processo può essere descritto statisticamente usando le Catene di Markov.

Nel caso di un automa a stati finito non deterministico (in inglese NFA), un nuovo input può portare la macchina in numero di stati maggiore di uno. Questo è indicato nella tabella usando un paio di parentesi graffe { } con all'interno l'insieme degli stati di destinazione.

Trasformazione della tabella in diagramma di stato e viceversa

È possibile disegnare un diagramma di stato a partire dalla tabella. La sequenza dei passi è la seguente:

1. disegnare i cerchi che rappresentano gli stati
2. per ogni stato, leggere tutte le righe e disegnare una freccia per ogni stato (o stati) di destinazione.
3. attribuire il nome di stato iniziale
4. attribuire il nome di stato di accettazione ad uno o più stati