State diagram
|
|
State diagrams are used to graphically represent finite state machines. State transition tables are another possible representation.
There are many forms of state diagrams that differ slightly and have a different semantics.
| Contents |
Directed graph
A classic form of a state diagram for a finite state machine is a directed graph where
- each edge is a transition between two states
- For a deterministic finite state machine (DFA), nondeterministic finite state machine (NFA), generalized nondeterministic finite state machine (GNFA), or Moore machine, input is signified on each edge
- For a Mealy machine, input and output are signified on each edge
- each vertex is a state
- For a Moore machine, output is signified on each state
In practice, vertices are normally represented by circles and, if needed, double circles are used for accept states.
Examples
DFA, NFA, GNFA, or Moore machine
S1 and S2 are states and S1 is an accept state. Each edge is labeled with the input.
- Missing image
DFAexample.png
Mealy machine
S0, S1, and S2 are states. Each edge is labeled with "j / k" where j is the input and k is the output.
- Missing image
Mealymachine_jaredwf.png
Harel statechart
Harel statecharts (developed in 1987 by David Harel) are gaining some more widespread usage since a variant has become part of UML. The diagram type allows to model superstates, concurrent state diagrams and e.g. to model activities as part of a state.
Classic state diagrams are so called "or" diagrams, because the machine can only be in one state or the other. With Harel statecharts it is possible to model "and" machines, where a machine is in two or more states at the same time. This is due to the possibility of having superstates.
Ward and Mellor statecharts
References
- David Harel's home page (http://www.wisdom.weizmann.ac.il/~dharel/)
- D. Harel. Statecharts: A visual formalism for complex systems. Science of Computer Programming, 8(3):231--274, June 1987. (http://www.wisdom.weizmann.ac.il/~dharel/SCANNED.PAPERS/Statecharts.pdf)ru:Диаграмма состояний