State diagram

State diagram

State diagrams is a diagram used in the field of computer science, representing the behavior of a system, which is composed of a finite number of states. There are many forms of state diagrams, which differ slightly and have different semantics.


State diagrams are used to describe the behavior of a system. State diagrams can describe the possible states of an object as events occur. Each diagram usually represents objects of a single class and track the different states of its objects through the system. [ [ State Diagrams] . Retrieved 11 August 2008.]

State diagram can be used to graphically represent finite state machines. This was introduced by 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 a state diagram for a finite state machine is a directed graph with the following elementsTaylor Booth (1967) "Sequential Machines and Automata Theory", John Wiley and Sons, New York.] John Hopcroft and Jeffrey Ullman (1979) "Introduction to Automata Theory, Languages, and Computation", Addison-Wesley Publishing Company, Reading Mass, ISBN 0-201-02988-X] :

*States Q: a finite set of vertices normally represented by circles and labelled 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 input symbols into output symbols, denoted mathematically as ω : Σ × QZ.

*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. This mapping describes the state transitions that is to occur on input of a particular symbol. This is written mathematically as δ : Σ × QZ
*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 textsEdward J. McClusky, Introduction to the Theory of Switching Circuits, McGraw-Hill, 1965] , 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 state machine (DFA), nondeterministic finite state machine (NFA), generalized nondeterministic finite state machine (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. Each edge is labeled with the input. This example shows an acceptor for strings over {0,1} 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 David Harel, [ Statecharts: A visual formalism for complex systems. Science of Computer Programming] , 8(3):231--274, June 1987.] are gaining widespread usage since a variant has become part of the Unified Modeling Language. The diagram type allows the modeling of superstates, concurrent states, and activities as part of a state.

Classic state diagrams are "or" (disjunctive) diagrams, because the machine can only be in one of all the possible states. With Harel statecharts it is possible to model "and" machines, where a machine can be in two or more states concurrently. This is due in part to the modelling of superstates and in part to the modelling of concurrent machines.

UML state diagram

The Unified Modeling Language (UML) state diagram is essentially a Harel statechart with standardized notation D. Drusinsky, [ "Modelling and verification using UML statecharts"] , Elsevier, 2006] , which can describe many systems, from computer programs to business processes. The following are the basic notational elements that can be used to make up a diagram:

* 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 before a "/" and enclosed in square-brackets ( "eventName" [guardExpression] ), 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.

According to PiloneDan Pilone, UML 2.0 Pocket Reference, O'Reilly, 2006] , the only predefined guard condition is ELSE. No other examples are provided within that publication.

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.

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.

See also

* SCXML an XML language that provides a generic state-machine based execution environment based on Harel statecharts.
* David Harel


External links

* [ Introduction to UML 2 State Machine Diagrams] by Scott W. Ambler
* [ UML 2 State Machine Diagram Guidelines] by Scott W. Ambler
* [ Practical Statecharts in C/C++] by Miro Samek
* [ Practical UML Statecharts in C/C++, 2nd Edition] by Miro Samek
* [ Round-trip Engineering State Charts]
* [ sinelaboreRT] - generates human readable c-code from state-charts especially targeting embedded real-time systems
* [ Advanced State Management] - video introduction to state charts and thinking in hierarchical states.

Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • state diagram — būsenos diagrama statusas T sritis chemija apibrėžtis Pusiausvirųjų fazių savybes apibūdinančių termodinaminių parametrų tarpusavio priklausomybės grafinis vaizdas. atitikmenys: angl. constitution diagram; constitutional diagram; equilibrium… …   Chemijos terminų aiškinamasis žodynas

  • state diagram — būsenų diagrama statusas T sritis automatika atitikmenys: angl. state diagram vok. Zustandsdiagramm, n rus. диаграмма состояний, f pranc. diagramme d états, m …   Automatikos terminų žodynas

  • state diagram — būsenos diagrama statusas T sritis Standartizacija ir metrologija apibrėžtis Pusiausvirųjų fazių savybes apibūdinančių termodinaminių parametrų tarpusavio priklausomybės grafinis vaizdas. atitikmenys: angl. state diagram vok. Zustandsdiagramm, n… …   Penkiakalbis aiškinamasis metrologijos terminų žodynas

  • state diagram — būsenos diagrama statusas T sritis Standartizacija ir metrologija apibrėžtis Termodinaminės sistemos pusiausvirųjų būsenų geometrinis vaizdas. atitikmenys: angl. state diagram vok. Zustandsdiagramm, n rus. диаграмма состояния, f pranc. diagramme… …   Penkiakalbis aiškinamasis metrologijos terminų žodynas

  • state diagram — būsenos diagrama statusas T sritis fizika atitikmenys: angl. state diagram vok. Zustandsdiagramm, n rus. диаграмма состояния, f pranc. diagramme d’état, m …   Fizikos terminų žodynas

  • State Diagram — Der Begriff Zustandsdiagramm entstammt der Systemtheorie. Er bezeichnet die grafische Darstellung von Zuständen und daran anknüpfenden Zustandswechseln. Er findet Verwendung in mehreren Bereichen: In der Informatik ist das… …   Deutsch Wikipedia

  • State transition table — In automata theory and sequential logic, a state transition table is a table showing what state (or states in the case of a nondeterministic finite automaton) a finite semiautomaton or finite state machine will move to, based on the current state …   Wikipedia

  • Diagram — Further information: Chart Sample flowchart representing the decision process to add a new article to Wikipedia. A diagram is a two dimensional geometric symbolic representation of information according to some visualization technique. Sometimes …   Wikipedia

  • State variable — A state variable is an element of the set of variables that describe the state of a dynamical system.In case of simple mechanical systems, position coordinates and their derivates are typical state variables. Temperature, pressure, internal… …   Wikipedia

  • State (computer science) — In computer science and automata theory, a state is a unique configuration of information in a program or machine. It is a concept that occasionally extends into some forms of systems programming such as lexers and parsers. Whether the automaton… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”