(Last modified Fri Jun 06 19:11 2008)

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]. 

An FSM models behavior by presenting states and transitions between them; each transition is associated with an input event to the FSM (or possibly the empty event, in the case of nondeterministic FSMs).  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 on states only can be automatically transformed into an equivalent one with actions on transitions only, 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 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.  Statecharts are now part of the OMG UML standard (OMG Unified Modeling Language Specification (2003)), from which most of the figures are drawn. 

"In all airborne states, when yellow handle is pulled seat will be ejected"  (clustering)	"gearbox change of state is independent of braking system"  (orthogonality)	"display-mode consists of time-display, date-display, and stopwatch-display"  (refinement)

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). 

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. 

• Composite state Active contains many substates. 
• 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 circle (see next diagram for an example). 
• Input events that trigger transitions between states may be:
  • just names ("connected") whose meaning is defined elsewhere; 
  • parameterized ("dial digit (n)") to stand for any of several related events ("dial 1", "dial 2", etc. in this case); 
  • time delays ("after (15 sec.)"); 
  • restricted by guard conditions in square brackets [ ] ("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 / ("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 ("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). 

• The composite state "Dialing" contains three substates ("Start", "Partial Dial", and the 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). 

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

• 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". 

• 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. 

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

• 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.

A synchronization state indicates that concurrent substates may have to pause to synchronize before moving to their following states.  (The "*" in it has some significance but I am not sure what.) 

References

[Harel1987-svfc]  David Harel.  "Statecharts: A visual formalism for complex systems".  Science of Computer Programming 8[3] pp. 231-274, June 1987.

OMG Unified Modeling Language Specification (2003). 

Thomas A. Alspaugh
Assistant Professor, Informatics Dept.
School of Information and Computer Sciences