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
[modifica | modifica wikitesto]Tabella di stato ad una dimensione
[modifica | modifica wikitesto]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 | modifica wikitesto]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.
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.
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 | modifica wikitesto]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 | modifica wikitesto]Un esempio di tabella di transizione di stato per una macchina M e del corrispondente diagramma di stato è il seguente:
| 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 | modifica wikitesto]È 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
Note
[modifica | modifica wikitesto]- ^ (EN) Michael Breen, Experience of using a lightweight formal specification method for a commercial embedded system product line∗ (PDF), 29 Aprile 2005, DOI:10.1007/s00766-004-0209-1.
- ^ (EN) Requirements Specification for Process-Control Systems (PDF), su sunnyday.mit.edu, 9 settembre 1994.