State diagram

A state diagram is a type of diagram used in computer science and related fields to describe the behavior of systems. State diagrams require that the system described is composed of a finite number of states; sometimes, this is indeed the case, while at other times this is a reasonable abstraction. Many forms of state diagrams exist, which differ slightly and have different semantics.

State diagrams are used to give an abstract description of the behavior of a system. This behavior is analyzed and represented as a series of events that can occur in one or more possible states. Hereby "each diagram usually represents objects of a single class and track the different states of its objects through the system".

State diagrams can be used to graphically represent finite state machines. This was introduced by C.E. Shannon and W. Weaver in their 1949 book "The Mathematical Theory of Communication". Another source is Taylor Booth in his 1967 book "Sequential Machines and Automata Theory". Another possible representation is the State transition table.

A classic form of state diagram for a finite state machine or finite automaton (FA) is a directed graph with the following elements (Q,Σ,Z,δ,q₀,F):

The output function ω represents the mapping of ordered pairs of input symbols and states onto output symbols, denoted mathematically as ω : Σ × Q→ Z.

For a deterministic finite automaton (DFA), nondeterministic finite automaton (NFA), generalized nondeterministic finite automaton (GNFA), or Moore machine, the input is denoted on each edge. For a Mealy machine, input and output are signified on each edge, separated with a slash "/": "1/0" denotes the state change upon encountering the symbol "1" causing the symbol "0" to be output. For a Moore machine the state's output is usually written inside the state's circle, also separated from the state's designator with a slash "/". There are also variants that combine these two notations.

...
Wikipedia