See Also

State diagram

State diagrams are used to graphically represent finite state machine Finite state machine

A finite state machine or finite automaton is a model of behavior composed of state [i]s, ... 

s. State transition table State transition table

In Automata Theory [i], a state transition table is a table describing the transiti ... 

s are another possible representation. There are many forms of state diagrams that differ slightly and have different semantics.

Discussions

  Discussion Features

   Ask a question about 'State diagram'

   Start a new discussion about 'State diagram'

   Answer questions about 'State diagram'

   'State diagram' discussion forum


Encyclopedia

State diagrams are used to graphically represent finite state machine Finite state machine

A finite state machine or finite automaton is a model of behavior composed of state [i]s, ... 

s. State transition table State transition table

In Automata Theory [i], a state transition table is a table describing the transiti ... 

s are another possible representation.

There are many forms of state diagrams that differ slightly and have different semantics.

Directed graph


A classic form of a state diagram for a finite state machine Finite state machine

A finite state machine or finite automaton is a model of behavior composed of state [i]s, ... 

 is a directed graph Directed Graph

Sorry, no overview for this topic 

 with the following elements:

States Q: a finite set of vertices normally represented by circles and labelled with unique designator symbols or words written inside them .

Input symbols S: a finite collection of input "symbols" or designators S . For a deterministic finite state machine Deterministic finite state machine

In the theory of computation [i], a deterministic finite state machine or deterministic finite automa ... 

 , nondeterministic finite state machine Nondeterministic finite state machine

In the theory of computation [i], a nondeterministic finite state machine or nondeterministic finite ... 

 , generalized nondeterministic finite state machine , or Moore machine Moore machine

In the theory of computation [i], a Moore machine is a finite state automaton [i] where the outputs are ... 

, input is signified on each edge, usually near the originating state. For a Mealy machine Mealy machine

[i], a [[finite state machine]... 

, input and output are signified on each edge usually shown separated with a slash "/":
Mealy input and output labels on an edge : "1/0" designates symbol "1" caused symbol "0" as output.


Output symbols Z: a finite collection of output "symbols" or designators . For a Mealy machine Mealy machine

[i], a [[finite state machine]... 

, input and output are signified on each edge as shown above. For a Moore machine Moore machine

In the theory of computation [i], a Moore machine is a finite state automaton [i] where the outputs are ... 

 the state's output is usually written inside the state's circle, separated from the state's designator with a slash "/".

Example: If a state has a number of outputs the diagram should reflect this : e.g. "q5/1,0" designates state q5 with outputs a=1, b=0. This designator will be written inside the state's circle.


The "Output function ?" represents the mapping ? of input symbols I x states Q into output symbols Z .

Edges d: represent the "transitions" between two states as caused by the input . An 'edge' is usually drawn as an arrow directed from the present-state toward the next-state. d represents the mapping of input symbols I x states Q onto output symbols Z .

Start state qo: . The start state qo is usually represented by an "arrow pointing at it from nowhere" . In older texts the start state is not shown and must be inferred from the text.

Accepting state F: If used -- a collection of double circles used to designate accept state Finite state machine

A finite state machine or finite automaton is a model of behavior composed of state [i]s, ... 

s . Sometimes the accept state function as "Final" 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.


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.


Harel statechart


Harel statecharts are gaining some more widespread usage since a variant has become part of UML Unified Modeling Language

In software engineering [i], the Unified Modeling Language is a non-proprietary [i] ... 

. 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



The Unified Modeling Language Unified Modeling Language

In software engineering [i], the Unified Modeling Language is a non-proprietary [i] ... 

  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 Petri net

A Petri net is one of several mathematical [i] representation [i]s of discrete ... 

.

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

  • by Scott W. Ambler
  • by Scott W. Ambler
  • SCXML SCXML

    SCXML stands for State Chart XML : State Machine Notation for Control Abstraction.... 

     an XML language that provides a generic state-machine based execution environment based on Harel statecharts State diagram

    State diagrams are used to graphically represent finite state machine [i]s. ... 

    .
  • Modelling and verification using UML statecharts, Drusinsky, D., Elsevier Elsevier

    Elsevier, the world's largest publisher [i] of medical [i] and scientific literature [i], forms part of ... 

    , 2006,


  • Michael Sipser Michael Sipser

    Michael Sipser is a professor [i] of Applied Mathematics [i] in the Theory of Computation Group [i] at t ... 

     , Introduction to the Theory of Computation, Second Edition, Thomson Course Technology, Boston. ISBN-13: 978-0-534-95097-2, ISBN-10: 0-534-95097-3.


  • John Hopcroft John Hopcroft

    John E. Hopcroft is a renowned theoretical computer scientist [i].

... 

 and Jeffrey Ullman  Introduction to Automata Theory, Languarges, and Computation, Addison-Wesley Publishing Company, Reading Mass, ISBN 0-201-02988-X.

  • Taylor Booth  Sequential Machines and Automata Theory, John Wiley and Sons, New York. Library of Congress Catalog Card Number: 67-25924.