State machine basics Copy link to clipboard

This is a short overview over basic state machine concepts. For a more thorough explanation, see What are State Machines?

Words and definitions Copy link to clipboard

A finite-state machine (FSM) or finite-state automaton (FSA, plural: automata), finite automaton, or simply a state machine as a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number of states at any given time. The FSM can change from one state to another in response to some external inputs; the change from one state to another is called a transition. An FSM is defined by a list of its states, its initial state, and the conditions for each transition.

A state diagram is one of many possible representations of an FSM. A state transition table would be different way to describe an FSM.

A statechart or Harel statechart is an extended form of the classic state diagram. The basic principles are the same, however. In this documentation, the term statechart usually denotes the graphical representation of an FSM.

The term state machine is a short form of finite-state machine. In this documentation, the term state machine usually pertains to the dynamic aspects of an FSM, i.e., it is more thought of as being executed, simulated etc. than being depicted.

Automata theory Copy link to clipboard

itemis CREATE was designed to create statecharts according to David Harel’s statechart theory. Harel statecharts have become part of the Unified Modeling Language (UML). Harel introduced a couple of extensions to conventional state diagrams, making them more concise and more readable.

Classic state diagrams Copy link to clipboard

Classic state diagrams describe finite-state machines and consist of the following things only:

• A (finite) set of possible states
• A start state
• An accepting or final state
• A set of transitions, connecting states
• A set of input symbols
• A set of output symbols
• An output function, mapping pairs of input symbols and states to output symbols

These parameters describe a finite-state machine completely.

Moore and Mealy machines Copy link to clipboard

In classic automata theory, two distinct types of finite-state machines exist:

• The Moore machine , where the output of the machine depends on its current state only.
• The Mealy machine , where the output of the machine depends on its current state and its input.

It is possible to transform these types of machine into each other, however, states, transitions and the output function need to be changed to achieve this.

Harel statecharts Copy link to clipboard

Harel statecharts extend the classic state diagrams by a couple of additional aspects, resulting in representations that need much less states and transitions, making them much more compact, expressive, manageable and comprehensible – though not as mathematically concise as Moore or Mealy machines.

Harel added the following notations, dealing with hierarchy, concurrency, and communication:

• Composite states and regions, containing nested states or regions.
• History states, allowing to re-enter a composite state or region at the point where it had been left.
• Orthogonal states, allowing to run state machines concurrently.
• Events, allowing for communication between orthogonal states.
• Variables, allowing to memorize values and reducing the necessary number of states drastically.
• Actions (output) can not only occur along transitions, but additionally inside of states, especially as entry actions or exit actions.
• Activities (operations), bridging the gap between a state machine and real-world behavior.

Since Harel statecharts are a superset of Mealy and Moore machines, it is possible to model all of these types in itemis CREATE.