Software Engineering
Home Planning Requirements Writing Hazard Analysis Requirement Analysis Config Control Software Design Software Testing Software Standards Basic Logic

Software Design - State Machines

State Machines allow the programmer to easily implement arbitrary logic.

Moore Machine

In a Moore machine, the next state is determined solely by the current state:

In pseudo-code, a Moore machine can be implemented using a simple static array:

States[0] = StateA
States[1] = StateB
States[2] = StateC
States[3] = StateD

Next_State = Current_State + 1
IF Current_State > 3 THEN Current_State = 0

Mealy Machine

A Mealy machine is more complex, in that the next state is determined by a [Current_State, Event] pairing. in other words, a Mealy machine produces an output for each transition.

This diagram shows six states (A - F) and ten transitions. in pseudo-code, the transition table would look like this:

[StateA, Start] => StateB
[StateB, Error] => StateD
[StateB, OK] => StateC
[StateC, OK] => StateC
[StateC, Recoverable_Error] => StateE
[StateC, Fatal_Error] => StateF
[StateD, Retry] => StateB
[StateD, Abort] => StateA
[StateE, N/A] => StateD
[StateF, Abort] => StateA

State C has a holding condition - the OK transition. This means that it remains in StateC until one of the two errors occurs.

States E could be a transitional state, such as a cleanup task prior to StateD. Its next state is pre-determined.

The holding state (such as [StateC, OK] ) could be implied for each state; that is, it remains in that state until a transition occurs.

The Transition table can be a static structure inside a function, whose purpose is to match the transition with the current state. If the state machine were an object, it could contain an attribute for the current state and a method to set the next state, with the transition event passed as a parameter. Traverse the transition table until the [State, Transition] pair is found, and obtain the next State.

One common issue in Mealy machines is handling concurrent transitions. For example, while in State C if both a Fatal and a Recoverable Error occur, which transition should be activated?

Another issue is states with no appropriate exit condition. For example, StateC has no normal exit, unless program termination is treated as a recoverable error. In contrast, in some embedded applications it may be desirable to hold the machine in a given state permanently; for example, removing the Abort transition from StateF to keep the machine in StateF, forcing the user to shutdown to recover from a fatal error.

Simple Mealy State Machine Using switch() statement

The simplest method of implementing a Mealy machine involves the use of a switch() statement to handle the events. Each possible State has a corresponging case in the switch() statement. Within each case, the specific Event is checked to see what action (if any) should be taken. This is suitable for very small state machines. Once the state machine involves more than a half-dozen states and events, it is probably simpler to use either a [State, Event] table method or the State Design Pattern.

Sample Code:

//--------------------------------------------------------------

// This is a simple shell for a state machine that has a few
// simple states and events.
// Based on the current state, what action should be taken?
// A variable ok will be set FALSE if the Event was not valid for the current State.
switch (m_State)
{
 //--------------------------------------------------------------
 case S_IDLE:  // IDLE state - waiting for file read to start
   if (Event == E_STARTFILE)      // Event : File read started
     m_State = S_WAIT_4_PARM;     // Set next state
   else
     ok = FALSE; // Unexpected event
   break;
 //--------------------------------------------------------------
 case S_WAIT_4_PARM:  // Reading file - wait for parm entries in file
   if (Event == E_STARTPARM)  // Event : parm entry in file
   {

      // Do action for this event
   } 
   else if (Event == E_STOPFILE)  // Event : End of file reached
   {

      m_State = S_IDLE;
   }
   else
      ok = FALSE;
   break;
} // END switch
             

What To Do With My State Machine?

From the perspective of the State itself, there are two transitions and one steady state:

  1. First Transition - Entering the State.
  2. Steady State - In the State.
  3. Second Transition - Leaving the State.

The Transition Table can define an OnEntry function and an OnExit function, which would handle any required activity upon entering and leaving the State.

Handling the Steady State is simple if the program in a procedural program that uses the "main loop" concept (such as most embedded applications or MS-DOS applications). However, if the program is an event driven program (such as a Windows application), then there really is no "steady state." In this case, the "steady state" function would be a means of handing a Windows event (such as a timer event or a character from an input stream).
For example, the Steady State function could accept characters from an input stream and direct them to their appropriate handler. Parsers use a state machine in this fashion, directing the characters depending on whether a token has started, is being collected, or has completed.