State diagrams are used to graphically represent finite state machines. State transition tables are another possible representation. Fig. ... In Automata Theory, a state transition table is a table describing the transition function T of a finite automaton. ...

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 is a directed graph with the following elements: Fig. ... This article just presents the basic definitions. ...

States Q: a finite set of vertices normally represented by circles and labelled with unique designator symbols or words written inside them (Booth (1967) p. 69, Hopcroft and Ullman (1979) p. 16, Sipser (2006) p. 34).

Input symbols Σ: a finite collection of input "symbols" or designators Σ (Booth, Hopcroft and Ullman, Sipser). 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, usually near the originating state. For a Mealy machine, input and output are signified on each edge usually shown separated with a slash "/": In the theory of computation, a deterministic finite state machine or deterministic finite automaton (DFA) is a finite state machine where for each pair of state and input symbol there is one and only one transition to a next state. ... In the theory of computation, a nondeterministic finite state machine or nondeterministic finite automaton (NFA) is a finite state machine where for each pair of state and input symbol there may be several possible next states. ... In the theory of computation, a generalized nondeterministic finite state machine or generalized nondeterministic finite automaton (GNFA) is a NFA where each transition may be labeled with any regular expression. ... Moore model: control of an elevator door In the theory of computation, a Moore machine is a finite state automaton where the outputs are determined by the current state alone (and not on the input). ... In the theory of computation, a Mealy machine is a finite state machine where the outputs are determined by the current state and the input. ...

Mealy input and output labels on an edge (arrow): "1/0" designates symbol "1" caused symbol "0" as output.

Output symbols Z: a finite collection of output "symbols" or designators ((Booth, Hopcroft and Ullman, Sipser)). For a Mealy machine, input and output are signified on each edge as shown above. For a Moore machine the state's output is usually written inside the state's circle, separated from the state's designator with a slash "/". In the theory of computation, a Mealy machine is a finite state machine where the outputs are determined by the current state and the input. ... Moore model: control of an elevator door In the theory of computation, a Moore machine is a finite state automaton where the outputs are determined by the current state alone (and not on the input). ...

Example: If a state has a number of outputs (e.g. "a= motor counter-clockwise=1, b= caution light inactive=0") 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 (Booth).

Edges δ: represent the "transitions" between two states as caused by the input (identified by their symbols drawn on the "edges"). An 'edge' is usually drawn as an arrow directed from the present-state toward the next-state. δ represents the mapping of input symbols I x states Q onto output symbols Z (Booth, Hopcroft and Ullman, Sipser).

Start state qo: (not shown in the examples below). The start state qo is usually represented by an "arrow pointing at it from nowhere" (cf Sipser (2006) p. 34, Hopcroft and Ullman (1979) p. 16). In older texts (e.g. Booth (1969), McCluskey (1965), Hill and Peterson (1974)) the start state is not shown and must be inferred from the text.

Accepting state(s) F: If used -- a collection of double circles used to designate accept states (Hopcroft and Ullman, Sipser). Sometimes the accept state(s) function as "Final" (halt, trapped) states (cf Hopcroft and Ullman (1979) Figure 2.15, p. 33). In the theory of computation, an accept state (sometimes referred to as an accepting state) is a state at which the machine has successfully performed its procedure. ...

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.

Image File history File links DFAexample. ...

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.

Image File history File links A state diagram for a Mealy machine created by me. ...

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. 1987 (MCMLXXXVII) was a common year starting on Thursday of the Gregorian calendar. ... Prof. ... In the field of software engineering, the Unified Modeling Language (UML) is a non-proprietary specification language for object modeling. ...

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) (or SysML) state diagram is essentially a state diagram with standardized notation that can describe a lot of things, from computer programs to business processes. The following are the basic notational elements that can be used to make up a diagram: Image File history File links UML_state_diagram. ... Image File history File links UML_state_diagram. ... In the field of software engineering, the Unified Modeling Language (UML) is a non-proprietary specification language for object modeling. ... SysML, or Systems Modeling Language, is a general-purpose systems engineering modeling language. ...

• Filled circle, pointing to the initial state
• Hollow circle containing a smaller filled circle, indicating the final state (if any)
• Rounded Rectangle, denoting a state. Top of the rectangle contains a name of the state. Can contain a horizontal line in the middle, below which the activities that are done in that state are indicated
• Arrow, denoting transition. The name of the event (if any) causing this transition labels the arrow body. A guard expression may be added, enclosed in brackets( [] ) denoting that this expression must be true for the transition to take place. If an action is performed during this transition, it is added to the label following a "/". eventName[guardExpression]/action
• 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. A Petri net is a mathematical representation of discrete distributed systems. ...

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, [1]

• Michael Sipser (2006), 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 and Jeffrey Ullman (1979) Introduction to Automata Theory, Languarges, and Computation, Addison-Wesley Publishing Company, Reading Mass, ISBN 0-201-02988-X.

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

archana SCXML stands for State Chart XML : State Machine Notation for Control Abstraction. ... Statecharts originally invented by David Harel in 1984 are an extension to state machines. ... Elseviers logo. ... 2006 (MMVI), a common year starting on Sunday of the Gregorian calendar. ... Michael Sipser Michael Sipser is a professor of Applied Mathematics in the Theory of Computation Group at the Massachusetts Institute of Technology. ... John Hopcroft John E. Hopcroft (born October 7, 1939) is a renowned theoretical computer scientist and the grandson of Jacob Nist, founder of the Seattle Box Company. ... Jeffrey D. Ullman (born November 22, 1942) is a renowned computer scientist. ...