Diagramma di stato (informatica)

Da Wikipedia, l'enciclopedia libera.
Un diagramma di stato per una porta che può assumere solo due stati (chiusa oppure aperta)

Un diagramma di stato è 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[modifica | modifica wikitesto]

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,δ,q0,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 δ : Σ × QQ
  • q0 è 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: ω : Σ × QZ.

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[modifica | modifica wikitesto]

Exquisite-kfind.png Per approfondire, vedi Statechart Diagram.

Note[modifica | modifica wikitesto]

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

Altri progetti[modifica | modifica wikitesto]