Basic (non-hierarchical) State Machine

A state machine consists of a set of inputs and a set of states, one of which is the "current" state to which all input is directed until it decides to transition to another state, which then takes over as the current state. When a state receives an input it can do one of the following:
  • Transition To Another State When a transition occurs, the current state is known as the "source" and the other state is the "target". The source state is given a chance to perform an "exit" action and then the target state is given a chance to perform an "entry" action. In addition, an action can be associated with the transition; this action is called a "transition action" and occurs after the exit action and before the entry action. A state can transition to itself, in which case it performs the exit action and the entry action.
  • Perform An Action In the case the state performs an action associated with the input and that's it -- the state doesn't change, so no exit/entry actions are performed.
  • Do Nothing Exactly what it sounds like -- nothing happens. It's quite common to ignore certain inputs in certain states.

That's pretty much it! The whole point is that you've got a well-defined set of states that respond in well-defined ways to each input and execute a well-defined set of actions that occur at well-defined points in time. It's all that "well-defined" stuff that makes a state machine valuable as compared to just "writing the code" as we usually do when there are relatively few states and inputs.

Hierarchical State Machine

With a hierarchical machine, a state can have substates, one of which is designated as the "default". Whenever the parent state is entered, the default substate is automatically entered (this continues recursively if the substate has substates). Due to these automatic default transitions, a state with substates will never be the current state; only a "leaf" (a state with no substates) can be the current state.

Entry/Exit Actions
A superstate's entry actions are performed before a substate's entry actions. Exit actions are the opposite: the substate exit actions are performed before the superstate's exit actions. As a result, substates can take advantage of their superstates' actions and don't need to repeat them. This a key benefit that allows hierarchical machines to be simpler than basic machines.

Substates only have to deal with the inputs they wish to handle differently than their superstates; any actions not handled by substates are automatically passed along to their superstates. This is another key benefit that allows hierarchical machines to simplify complex scenarios.

Any state can transition to any other state regardless of whether it is a super- or sub-state. A good rule of thumb is to prefer transitions to superstates because by going directly to a substate you are getting into the business of the superstate. That said, there are often good reasons to transition directly to substates.

To determine which states will be exited and which will be entered when the transition occurs, it is necessary to determine the "Lowest Common Ancestor" (LCA) between the source and target states. It's exactly what it sounds like -- the first state that is an ancestor of both states. With the LCA identified, the source state is exited followed by each superstate up to (but not including) the LCA. Then, each substate down to and including the target state is entered. As before, transition actions are performed after the exit actions and before the entry actions.


That it's! Again, the power comes from the fact that the rules about entry, exit and transition actions are well-defined and (hopefully) intuitive. It should be noted the UML state machine spec works out to the order described here.

Last edited Feb 16, 2013 at 3:53 AM by MikeRiedel, version 12


No comments yet.