A state diagram is used in computer science and related fields to describe the behavior of systems. State diagrams require that the system 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.
Overview State diagrams provide an abstract description of a system's behavior. This behavior is analyzed and represented by 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 (also called finite automata). This was introduced by Claude Shannon and Warren 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.
Directed graph
A classic form of state diagram for a finite automaton (FA) is a directed graph with the following elements (Q, Σ, Z, δ, q0, F):
Vertices Q: a finite set of states, normally represented by circles and labeled with unique designator symbols or words written inside them Input symbols Σ: a finite collection of input symbols or designators Output symbols Z: a finite collection of output symbols or designators The output function ω represents the mapping of ordered pairs of input symbols and states onto output symbols, denoted mathematically as ω : Σ × Q→ Z.
Edges δ: represent transitions from one state to another 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 to the next state. This mapping describes the state transition caused by an input. This is written mathematically as δ : Q × Σ → Q, so δ (the transition function) in the definition of the FA is given by both the pair of vertices connected by an edge and the symbol on an edge in a diagram representing this FA. Item δ(q, a) = p in the definition of the FA means that from the state named q under input symbol a, the transition to the state p occurs in this machine. In the diagram representing this FA, this is represented by an edge labeled by a pointing from the vertex labeled by q to the vertex labeled by p. Start state q0: (not shown in the examples below). The start state q0 ∈ Q is usually represented by an arrow with no origin pointing to the state. In older texts, the start state is not shown and must be inferred from the text. Accepting state(s) F: If used, for example for accepting automata, F ∈ Q is the accepting state. It is usually drawn as a double circle. Sometimes the accept state(s) function as "Final" (halt, trapped) states. 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. For 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.
Example: DFA, NFA, GNFA, or Moore machine S1 and S2 are states and S1 is an accepting state or a final state. Each edge is labeled with the input. This example shows an acceptor for binary numbers that contain an even number of zeros.
Example: 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, invented by computer scientist David Harel, are gaining widespread usage since a variant has become part of the Unified Modeling Language (UML). The diagram type allows the modeling of superstates, orthogonal regions, and activities as part of a state. Classic state diagrams require the creation of distinct nodes for every valid combination of parameters that define the state. For all but the simplest of systems, this can lead to a very large number of nodes and transitions between nodes (state and transition explosion), which reduces the readability of the state diagram. With Harel statecharts it is possible to model multiple cross-functional state diagrams within the statechart. Each of these cross-functional state machines can transition internally without affecting the other state machines. The current state of each cross-functional state machine defines the state of the system. The Harel statechart is equivalent to a state diagram but improves its readability.
Alternative semantics There are other sets of semantics available to represent state diagrams. For example, there are tools for modeling and designing logic for embedded controllers. These diagrams, like Harel's original state machines, support hierarchically nested states, orthogonal regions, state actions, and transition actions.
State diagrams versus flowcharts Newcomers to the state machine formalism often confuse state diagrams with flowcharts. The figure below shows a comparison of a state diagram with a flowchart. A state machine (panel (a)) performs actions in response to explicit events. In contrast, the flowchart (panel (b)) automatically transitions from node to node upon completion of activities.
… excerpt ends here. Continue reading the full article.
