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 who differ slightly and have a different semantics. The following are examples:

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 DFA, NFA, 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.

Resources

D. Harel. Statecharts: A visual formalism for complex systems. Science of Computer Programming, 8(3):231--274, June 1987.

Ward and Mellor Statecharts