Diagramma di stato (informatica)

Un diagramma di stato (anche detto pallogramma) è un tipo di diagramma usato in informatica per descrivere il comportamento dei sistemi, il quale viene analizzato e rappresentato tramite una serie di eventi che potrebbero accadere per ciascun stato. Per poter essere realizzato, il sistema deve essere composto da un numero finito di stati; in alternativa, lo si può progettare tramite astrazione. Esistono diverse forme di diagramma di stato, che differiscono di poco tra loro ed hanno semantiche differenti, e possono essere descritti sia graficamente sia attraverso una tabella di transizione degli stati.

Nel linguaggio UML, il diagramma di stato raffigura gli oggetti di una classe e delinea i vari stati ad essi collegati all'interno del sistema^[1].

Il primo a descrivere in maniera grafica automi a stati finiti fu Taylor Booth nel 1967 nel suo libro intitolato Sequential Machines and Automata Theory.

Grafo orientato

Una tipica forma con cui vengono disegnati i diagrammi di stato per un automa a stati finiti è il grafo orientato, descritto dalla sestupla (Q,Σ,Z,δ,q₀,F)^[2]^[3], dove:

Q è l'insieme degli stati ed è un set finito di nodi del grafo, solitamente rappresentati da cerchietti ed etichettati al loro interno tramite simboli;
Σ è una collezione finita di simboli di input;
Z è una collezione finita di simboli di output;
δ rappresenta l'insieme degli stati prossimi, ovvero delle transizioni tra due stati a seguito di un input, le quali vengono identificate dai loro simboli riportati sugli archi orientati (ovvero le frecce), ed è esprimibile in forma matematica come δ : Σ × Q → Q
q₀ è lo stato iniziale, in genere segnalato da una freccia senza origine che punta su di esso (mentre in libri meno recenti non è indicato esplicitamente e deve essere dedotto dal testo^[2]^[4]);
F è lo stato finale, di solito indicato con un doppio cerchio concentrico.

La funzione di output ω rappresenta la mappatura delle coppie ordinate dei simboli di input e di stato verso quelli di output, denotata matematicamente come: ω : Σ × Q→ Z.

Nei casi dell'automa a stati finiti deterministico (DFA), dell'automa a stati finiti non deterministico (NFA), dell'automa a stati finiti non deterministico generalizzato (GNFA) e della macchina di Moore, su ciascun arco viene indicato solo l'input, mentre per una macchina di Mealy vengono segnalati sia l'input sia l'output, separati da una barra "/": ad esempio, "1/0" indica che per quello stato, quando l'ingresso vale 1, si avrà un'uscita pari a 0. In una macchina di Moore l'uscita dello stato viene generalmente scritta all'interno del cerchio che lo rappresenta e separata dal simbolo dello stato con una barra "/".

Esempio di diagramma di stato per DFA, NFA, GNFA e macchine di Moore

Esempio di diagramma di stato per macchine di Mealy

Diagramma di stato UML

Lo stesso argomento in dettaglio: Statechart Diagram.

Note

^ (EN) UML State Diagrams Archiviato il 5 novembre 2011 in Internet Archive.
^ ^a ^b (EN) Taylor Booth (1967) Sequential Machines and Automata Theory, John Wiley and Sons, New York.
^ John Hopcroft and Jeffrey Ullman (1979) Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Publishing Company, Reading Mass, ISBN 0-201-02988-X
^ (EN) Edward J. McClusky, Introduction to the Theory of Switching Circuits, McGraw-Hill, 1965