Tabella di transizione di stato

tabella usata nella descrizione degli automi

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

modifica

Tabella di stato ad una dimensione

modifica

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

S1 e S2 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

modifica

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

modifica

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.[1] 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.[2]

Esempio

modifica

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 S1 (la prima riga), e l'input successivo è il carattere 1, allora la macchina rimarrà nello stato S1. Se l'input è un carattere 0, la macchina eseguirà una transizione verso lo stato S2, come può essere visto nella seconda colonna. Nel diagramma, lo stesso comportamento può essere osservato con la freccia diretta da S1 verso S2, 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

modifica

È 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