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