|
Tabella di transizione di statoNella 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 formeTabella di stato ad una dimensioneLe 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:
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 dimensioniLe tabelle di transizione di stato sono tipicamente tabelle bidimensionali. Ci sono due forme comuni per queste tabelle:
(S: stato, E: evento, A: azione, —: transizione non ammessa)
(S: stato, E: evento, A: azione, —: transizione non ammessa) Ulteriori forme di rappresentazioneNella 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] EsempioUn esempio di tabella di transizione di stato per una macchina M e del corrispondente diagramma di stato è il seguente:
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È possibile disegnare un diagramma di stato a partire dalla tabella. La sequenza dei passi è la seguente:
Note
|
