State diagram

Encyclopedia : S : ST : STA : 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 different semantics.

Contents

1 Directed graph

1.1 Examples

1.1.1 DFA, NFA, GNFA, or Moore machine
1.1.2 Mealy machine

2 Harel statechart
3 UML state diagram
4 Other extensions
5 References

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

S₁ and S₂ are states and S₁ is an accept state. Each edge is labeled with the input.

Mealy machine

S₀, S₁, and S₂ are states. Each edge is labeled with "j / k" where j is the input and k is the output.

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.

UML state diagram

Example UML State diagram.

The Unified Modeling Language (UML) state diagram is essentially a state diagram with standardised notation that can describe a lot of things, from computer programs to business processes. The following tools can be used to make up a diagram:

Filled circle, denoting START. Not absolutely necessary to use
Hollow circle, denoting STOP. Not absolutely necessary to use
Rectangle, denoting state. Top of the rectangle contains a name of the state. Can contain a horizontal line in the middle, below which the activity is written that is done in that state
Arrow, denoting transition. An expression can be written on top of the line, enclosed in brackets( [] ) denoting that this expression must be true for the transition to take place
Thick horizontal line with either x>1 lines entering and 1 line leaving or 1 line entering and x>1 lines leaving. These denote join/fork, respectively.

Other extensions

An interesting extension is to allow arcs to flow from any number of states to any number of states. This only makes sense if the system is allowed to be in multiple states at once, which implies that an individual state only describes a condition or other partial aspect of the overall, global state. The resulting formalism is known as a Petri net.

Another extension allows the integration of flowcharts within Harel statecharts. This extension supports the development of software that is both event driven and workflow driven.

References

[David Harel's home page]
[D. Harel. Statecharts: A visual formalism for complex systems. Science of Computer Programming, 8(3):231--274, June 1987.]
[Introduction to UML 2 State Machine Diagrams] by Scott W. Ambler
[UML 2 State Machine Diagram Guidelines] by Scott W. Ambler
SCXML an XML language that provides a generic state-machine based execution environment based on Harel statecharts.
Modelling and verification using UML statecharts, Drusinsky, D., Elsevier, 2006, [link]

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.