Diagramma di stato (informatica)

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search
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]

  • Magnifying glass icon mgx2.svgLo stesso argomento in dettaglio: Statechart Diagram.

Note[modifica | modifica wikitesto]

  1. ^ (EN) UML State Diagrams Archiviato il 5 novembre 2011 in Internet Archive.
  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]