Tabella di transizione di stato
# 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
