# 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 | S$_1$ | S$_2$ | 1 |
| 0 | 0 | S$_2$ | S$_1$ | 0 |
| 0 | 1 | S$_1$ | S$_2$ | 0 |
| 0 | 1 | S$_2$ | S$_2$ | 1 |
| 1 | 0 | S$_1$ | S$_1$ | 1 |
| 1 | 0 | S$_2$ | S$_1$ | 1 |
| 1 | 1 | S$_1$ | S$_1$ | 1 |
| 1 | 1 | S$_2$ | S$_2$ | 0 |
S$_1$ e S$_2$ 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 | E$_1$ | E$_2$ | ... | E$_n$ |
| S$_1$ | — | S$_y$ / A$_j$ | ... | — |
| S$_2$ | — | — | ... | S$_x$ / A$_i$ |
| S$_m$ | S$_z$ / A$_k$ | — | ... | — |
(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 | S$_1$ | S$_2$ | ... | S$_m$ |
| S$_1$ | — | — | ... | E$_x$ / A$_i$ |
| S$_2$ | E$_y$ / A$_j$ | — | ... | — |
| S$_m$ | — | E$_z$ / A$_k$ | ... | — |
(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 :
| Tabella di transizione di stato Stato\Input 1 0 S$_1$ S$_1$ S$_2$ S$_2$ S$_2$ S$_1$ | 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$_1$ (la prima riga), e l'input successivo è il carattere 1, allora la macchina rimarrà nello stato S$_1$. Se l'input è un carattere 0, la macchina eseguirà una transizione verso lo stato S$_2$, come può essere visto nella seconda colonna. Nel diagramma, lo stesso comportamento può essere osservato con la freccia diretta da S$_1$ verso S$_2$, 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:
* disegnare i cerchi che rappresentano gli stati
* per ogni stato, leggere tutte le righe e disegnare una freccia per ogni stato (o stati) di destinazione.
* attribuire il nome di stato iniziale
* attribuire il nome di stato di accettazione ad uno o più stati