Home
Foundations
⁘
Mathematical
- Sets
- Relations
- Correspondences
- Ordered Sets
- Lattices
- Graphs
- Powersets
- Cartesian Products
- Binary Strings
- aia
- Greek &c.
Logic
Writing/Thinking
SWD
- Quotations
- Kinds
- Architecture
- Data Flow
- Evolution
- IP
- Object Orientation
- Process
- Reviewing
- Testing
Requirements
- Kinds
- Quick Start
- Glossaries
- Goals
- i*
- Ilities
- Narratives
- SCR
- Tracing
Specifications
- Alloy
- E-R
- MSCs
- Statecharts
- UML
Java
Web
- (X)HTML
- XML Schemas
- XSLT
- MathML

Thomas A. Alspaugh

Statecharts

Statecharts are a formalism invented by David Harel in order to address some of the limitations of classical notations for finite state machines (FSMs) in describing complex systems (Harel1987-svfc). Statecharts are now part of the OMG UML standard (OMG2003-umls).

Finite state machines (FSMs)

An FSM models behavior by presenting states and transitions between the states; each transition is associated with an input event to the FSM (or possibly the empty event, in the case of nondeterministic FSMs). There are a finite number of states. The transitions available from each state correspond to the possible events expected in that situation, and each state represents all the possible histories of events that can lead up to that state.

Actions can be associated with states and/or transitions. The FSM can produce a particular action every time a particular state is entered, or exited, or while the FSM is in that state; and/or the FSM can produce a particular action every time a particular transition is taken. Actions on states and actions on transitions work equally well, and an FSM with actions only on states can be automatically transformed into an equivalent one with actions only on transitions, and vice versa.

FSMs have the advantage of conceptual simplicity, computability, and an intuitive diagram form, but the number of states and transitions required to model behaviors increases rapidly as the behaviors become more complex. This rapid increase is termed state explosion and is a serious disadvantage of FSMs for modelling anything beyond simple behavior.

Statecharts

Statecharts are a notation that addresses the state explosion problem by adding these features to FSMs:

clustering of states into superstates (termed composite states): the clustered states share the superstate's input and output transitions.
orthogonality between groups of states: the groups of states run independently in paralllel.
refinement of states: the inverse of clustering.

The examples below illustrate these features of the notation.

Feature	A situation in which it arises (Harel1987-svfc p.233)	A Statechart illustrating the feature
Clustering	In all airborne states, when yellow handle is pulled seat will be ejected
Orthogonality	Gearbox change of state is independent of braking system
Refinement	Display-mode consists of time-display, date-display, and stopwatch-display

As with any FSM, there are states, transitions between states and the events that cause them, and actions.

A state is an equivalence class of paths through the state machine: it represents all the paths by which you can reach that state. They have to be equivalent because once you reach that state, there is no record of how you got there, so whatever you do next depends only on that you are there in the state.

A transition is something that can happen next, once you are in a state. A transition occurs when its event happens.

An action is something the state machine makes happen in the world. Whereas states and transitions are of the state machine, events and actions are of the world. The events and actions are the ways (the only ways) the state machine interacts with the world it is in. An action can be attached to a transition, so that it is performed when that transition is taken; or to a state, so that it is performed when the state is entered, during the state, or when the state is exited (Statecharts use entry/action, do/action, and exit/action to distinguish these).

An event is something that makes a transition happen. In Statecharts, an event is written inputEvent[guard]/action, with all three parts optional. The inputEvent is what happens in the outside world that triggers the transition. An empty inputEvent means that the transition is taken immediately (if the guard is true at that time). The guard is a logical formula that filters out inputEvents; an inputEvent that occurs when its guard is false is ignored, permanently. An empty guard (the empty string instead of [condition]) represents true. The action can be empty (in which case the / is omitted too).

Using the features of Statecharts

As with any state machine, you can consider whether you need to add a new state, or combine two states into one.

If you find that when you get to a state, sometimes one action is appropriate and other times another action is, then you need to split the state into two (one with each action), and you need to arrange the transitions into them so that you reach the appropriate state at the appropriate times.
If you find there are two states with the same actions and with transitions leading to the same subsequent states, then you should combine those two states as they are not both needed and are just complicating the specification.

OMG2003-umls fig. 3-71

Composite state Active contains many substates (DialTone, Timeout, Dialing, Pinned, Talking, …).
The Active state is entered through the lift receiver event, and begins with the DialTone substate (indicated by the initial pseudostate popsicle ).
Because Active has no final state, all its substates may exit through the superstate transition event caller hangs up. A final pseudostate is shown as a popsicle with a concentric ring (see next diagram for an example).
Input events that trigger transitions between states may be:
- just names (e.g. connected) whose meaning is defined elsewhere;
- parameterized (e.g. dial digit (n)) to stand for any of several related events (dial 1, dial 2, etc. in this case);
- time delays (e.g. after (15 sec.));
- restricted by guard conditions in square brackets [ ] (e.g. dial digit(n) [incomplete]) so that only those occurrences of events when the guard is true are indicated; the meaning of the condition is defined elsewhere;
- the change of a condition from false to true. Denoted by when(BooleanExpression); and/or
- associated with actions performed when the transition occurs; the action is preceded by a slash / (e.g. lift receiver / get dial tone, with lift receiver the event that triggers the transition and get dial tone the action that occurs as a result) and the meaning of the action is defined elsewhere.
If an event, guard, and action are present, the syntax is event [guard] / action .
States may have actions that are performed in that state (e.g. do / play dial tone). The action label do indicates the action is performed continuously while the FSM is in the state. Action labels can be
- entry (perform on entry to the state),
- do (perform continuously throughout the state),
- include (the action is the name of a sub-statechart that starts running on entry to the state),
- exit (perform on exit from the state), or
- an event name (perform if/when the event occurs while in the state).

OMG2003-umls fig. 3-73

The composite state Dialing contains three substates (Start, Partial Dial, and the anonymous final state).
The initial pseudostate isn't a state; it just indicates the first state.
The action label entry indicates the action is performed when the state is entered (entry / start dial tone).
The action label exit indicates the action is performed when the state is left (exit / stop dial tone).
The guard [number.isValid()] prevents that transition from occurring unless the guard condition is true (here, the guard name seems to indicate that the guard prevents the transition unless the number dialed is valid).

OMG2003-umls fig. 3-74

This state contains a little symbol dumbbell (representing two blank states connected by a transition) indicating it is a composite state composed of substates that are not shown.

OMG2003-umls fig. 3-75

This composite state named Incomplete contains three concurrent substates, separated by dashed lines.
The three concurrent substates run at the same time.
The transition into the Incomplete composite state is distributed across all three substates, as though there were separate arrows from Incomplete's input pseudostate to Lab1, Term Project, and Final Test. Consequently, each one's initial state is entered simultaneously.
Each substate has a final pseudostate, and the superstate transition to Passed is distributed across all three substates. This is the same as if there were a transition from Lab2 to Passed at the event lab done, a transition from Term Project to Passed at the event project done, a transition from Final Test to Passed at the event pass. Because the three concurrent processes are substates of the same composite state, the Passed state begins when all three substates have terminated.
It is also possible to fail this class, by failing the final test. However, failing the project or either lab cannot result in failing the class because there is no transition from those states to Failed.

OMG2003-umls fig. 3-77

In this diagram, synchronization bars () are used to indicate synchronization of transitions in two or more concurrent processes.
The first synchronization bar indicates a fork in which the transitions to the two concurrent following states (A1 and B1) occur simultaneously.
The second synchronization bar indicates a join in which the transitions to the following state Cleanup from the predecessor states (A2 and B2) occur simultaneously.
Contrast this with the previous example, in which the following state Passed was entered after all the transitions from Lab2, Term Project, and Final Exam had occurred, but those three transitions (and any actions associated with them) did not have to be simultaneous. The synchronization bar forces the transitions themselves to occur simultaneously.
The composite state's name (Process) can be given in a tab rather than in the state.

OMG2003-umls fig. 3-78

The lower diagram is an abstraction of the upper one, with the internal substates of state W suppressed.
The little symbol indicates that substates exist but they are not being shown.
The small vertical bars () are stubs serving to terminate transition arrows that connect to internal states.
The transitions connected to the internal start pseudostate and final state do not need stubs, as they connect to the superstate.

A junction point () can be used to represent a cluster of arrows between groups of states. In this example, the junction point indicates possible transitions from State0 or State1 to either State2, State3, or State4.
A white-filled junction point indicates that the conditions on the second arrows may be affected by actions on the first arrows

OMG2003-umls fig. 3-81

OMG2003-umls fig. 3-80

OMG2003-umls fig. 3-82

This diagram shows a state whose internal states are defined elsewhere in (in a state named FailureSubmachine).
Stubs are used to connect to particular states of the included state.