Nella teoria degli automi e nella logica sequenziale , una tabella di transizione di stato è una tabella che mostra in quale stato (o stati nel caso di una macchina a stati finiti non deterministica ) di una macchina a stati muoversi, in base allo stato corrente e ad altre voci. Una tabella di stato è essenzialmente una tabella di verità, in cui alcuni degli ingressi sono lo stato corrente e le uscite includono lo stato successivo, insieme alle altre uscite.
Una tabella di stato è uno dei mezzi per specificare un automi finiti , altri mezzi sono un diagramma di transizione di stato e un'equazione caratteristica .
Conosciute anche come tabelle delle caratteristiche , le tabelle di stato unidimensionali assomigliano molto più alle tabelle della verità che alle versioni bidimensionali. Gli ingressi sono generalmente posti a sinistra e separati dalle uscite, che si trovano a destra. Le uscite rappresentano lo stato successivo della macchina.
Ecco un semplice esempio di una macchina a stati con due stati e due ingressi combinatori:
A | B | Stato attuale | Stato successivo | Uscita |
---|---|---|---|---|
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 molto probabilmente rappresentano i bit 0 e 1 semplici, perché un singolo bit può avere solo due stati.
Le tabelle di transizione di stato sono generalmente tabelle bidimensionali. Ci sono due forme comuni per disporli.
Evento di stato |
E 1 | E 2 | ... | E n |
S 1 | - | A y / S j | ... | - |
S 2 | - | - | ... | A x / S i |
... | ... | ... | ... | ... |
S m | A z / S k | - | ... | - |
(S: Stato, E: Evento, A: azione, -: passaggio illegale)
prossima corrente |
S 1 | S 2 | ... | S m |
S 1 | - | - | ... | A x / E i |
S 2 | A y / E j | - | ... | - |
... | ... | ... | ... | ... |
S m | - | A z / E k | ... | - |
(S: Stato, E: Evento, A: azione, -: transizione impossibile)
Transizioni simultanee in più macchine a stati finiti possono essere mostrate in quella che è effettivamente una tabella di transizione di stato n-dimensionale in cui coppie di righe mappano gli stati correnti (insiemi di) agli stati successivi. È un'alternativa alla rappresentazione della comunicazione tra macchine con stati interdipendenti.
All'altro estremo, sono state utilizzate tabelle separate per ciascuna delle transizioni in una singola macchina a stati: le tabelle "AND / OR" sono simili alle tabelle delle decisioni incomplete in cui la decisione relativa alle regole presenti è implicitamente l attivazione della transizione associata .
Di seguito viene fornito un esempio di una tabella di transizione di stato per una macchina '' 'M' '' con il diagramma di stato corrispondente.
|
Diagramma di transizione di stato ![]() |
Tutte le possibili voci della macchina sono elencate nelle colonne della tabella. Tutti gli stati possibili sono elencati nelle righe. Con la tabella di transizione di stato sopra, è facile vedere che se la macchina è nello stato S 1 (la prima riga) e la voce successiva è 1 , la macchina rimarrà nello stato S 1 . Uno 0 consente alla macchina di avviare una transizione allo stato S 2 come indicato nella seconda colonna. Questo è ciò che è rappresentato nel diagramma dalla freccia che va da S 1 a S 2 contrassegnata da uno 0 .
Nel caso di un automa finito non deterministico (NFA), una nuova voce può mettere la macchina in più stati, da qui il suo nome non deterministico. Ciò è indicato in una tabella di transizione di stato da una coppia di parentesi graffe {} con l'insieme degli stati obiettivo all'interno.
Un esempio è dato seguito.
Ingressi di stato |
1 | 0 | ε |
S 1 | S 1 | {S 2 , S 3 } | Φ |
S 2 | S 2 | S 1 | Φ |
S 3 | S 2 | S 1 | S 1 |
Qui, una macchina non deterministica nello stato S 1 che legge un ingresso di 0 , si troverà in due stati contemporaneamente, gli stati S 2 e S 3 . L'ultima colonna definisce la transizione legale degli stati di specificità, ε. Questo carattere speciale consente alla macchina di passare a uno stato diverso senza ricevere alcun input. Nello stato S 3 , l'NFA può passare a S 1 senza consumare un carattere di input. I due casi precedenti rendono l'automa descritto un automa finito non deterministico.
È possibile disegnare un diagramma di stato dalla tabella. Di seguito viene fornita una sequenza di passaggi facile da seguire: