Designing With State Machines

I can still remember the first time I was introduced to state machines. It was around 1988 when I took a course on compiler design. We used "The Dragon Book,"otherwise known as "Compilers: Principles, Techniques, and Tools."

State Machines

One of the assignments was to build a lexical analyzer (a piece of code that reads texts and turns it into meaningful tokens) to scan through a language called "Babbage."  To do this, we were tasked to build a state machine. If you aren't familiar with state machines, the best way to describe them is that you have a graph of different "states" with "transitions" that move between them.  The following shows a simple state machine that recognizes the words "cat," "cap," and "cub."

State machines are applicable across many different fields.  We already have seen them in relation to tokenizing input, but they can also be used in machine control.  Consider the following state machine that could be part of a simple thermostat.

In this state machine, there are three states: Heating, Cooling, and Idle.  If the system is in the idle state, and "TooCold" is declared, the state machine transitions to the Heating state. Likewise, if the system is in the Heating state and the target temperature is reached ("TargetReached"), the system transitions back to the Idle state.

Compound States

If you look at the thermostat state machine, you will see that it only handles heating and cooling. There is nothing in the state machine that controls the fan on the system. In the following diagram, the FanOn and FanOff states have been added along with a Wait state to introduce hysteresis to the system.

Reading the diagram, we see that when we are in the Idle state we are also in the FanOff state. When we are in the Heating, Wait, or Cooling states, we are also in the FanOn state. We don't need extra transitions to go between the FanOff and FanOn states. The transition to FanOn is automatically made when entering Heating or Cooling, and the transition to FanOff is made automatically when entering Idle.

Knowing what a state machine is is one thing. Knowing how to use them in code is another.

Working With State Machines in Code

There are several ways that we can implement state machines in code. I'll start with a brute force method, then move on successively simpler methods.

Logic Driven State Machines

The first method is through brute force coding of the state machine in the code itself. Switch statements and conditionals are used to control the state transitions. This is one of the first ways I started using state machines, and the method can still be found some "big loop" style control code. Let's look at what this would look like in terms of our first (simplest) thermostat:

    /// Brute Force

    switch (currentState) {

    case Idle:

        if (TooCold) {

            nextState = Heating;

        }

        else if (TooHot) {

            nextState = Cooling;

        }

        break;

    case Heating:

    case Cooling:

        if (TargetReached) {

            nextState = Idle;

        }

        break;

    }

    currentState = nextState;

The code doesn't look too bad for only three states, but consider what it would be like for our simple lexical analyzer!  There must be a better way!

Table Driven State Machines

I need to be honest here, for the lexical analyzer assignment I drew a state machine. Instead, I used a piece of software called "lex." "lex" builds a lexical analyzer state machine for you. It takes a set of words (tokens) to recognize and generates C code with state tables. Some might say I cheated, but the professor did not dock my grade.

Most people who code state machines will resort to a table approach. It works well for simple state machines with few states.

    /// Table

    const states stateTable[NUM_STATES][NUM_CONDITIONS] {

        /*              TooHot   TooCold  TargetReached */

        /* Idle    */  {Heating, Cooling, Idle},

        /* Heating */  {Idle,    Heating, Idle},

        /* Cooling */  {Cooling, Idle,    Idle}

    };

    newState = stateTable[currentState][condition];

The table is relatively concise and fast. There are no conditional tests, just simple table lookups.

Problems come when we get more states, need to deal with combined states (e.g. FanOn, FanOff), or try to change the table. Introduce a new state and/or condition, and everything needs to change.

What if we could have the speed of a table driven state machine and we could easily modify the state machine without having manually regenerate or modify the tables?

Graphically Driven State Machines

In case you missed it: I love programming for the Qt Framework. There are many reasons, but here is one of my favorites: 

Starting with Qt 5.7, you can draw state machines in Qt Creator and then easily export and use them in your code.

Modifying your state machine only costs you the rebuilding of your code, not hours of work re-coding brute force machines or modifying state tables.  Even combined states are handled gracefully.

Once you have graphically drawn your state machine, you just need to use it. You start by instantiating the state machine, then you simply connect the signals and slots as appropriate. The following code from my book Hands-On Embedded Programming with Qt shows how the thermostat state machine can be used.

    // Connect state machine states to UI indicators

    m_hvacSM.connectToState("Heating", ui->heatingInd, &QLabel::setEnabled);

    m_hvacSM.connectToState("Cooling", ui->coolingInd, &QLabel::setEnabled);

    m_hvacSM.connectToState("FanOn",   ui->fanInd,     &QLabel::setEnabled);

    // Connect state machine states to the HVAC controller

    m_hvacSM.connectToState("Heating", &m_hvacCtrl, &HVACController::setHeatingOn);

    m_hvacSM.connectToState("Cooling", &m_hvacCtrl, &HVACController::setCoolingOn);

    m_hvacSM.connectToState("FanOn",   &m_hvacCtrl, &HVACController::setFanOn);

    m_hvacSM.start();   // start the state machine

. . .

    // update the state machine based on current temp and the settings

    QString transition;

    if (temperature > ui->maxTemperatureSpinBox->value()) {

        transition = "TooHot";

    } else if (temperature < ui->minTemperatureSpinBox->value()) {

        transition = "TooCold";

    } else {

        transition = "TargetReached";

    }

    m_hvacSM.submitEvent(transition);

While it seems like the code is more complex, it is actually doing a lot more than the other examples. In the other examples, we only advanced the state machine. In this code example, we are also turning on GUI indicators, and we are causing the system to control the fan and heating and cooling elements. Best of all, changing the behavior of the system (like inserting a wait state) doesn't require re-writing the code! Only the state machine changes!

Behind the Scenes

Truth be told, both the second and third implementations are using tables. The real difference is in the second method we have to create and maintain the tables ourselves. In the third method, tooling takes our drawings, creates the tables, and provides a easy to use Qt/C++ Interface.

Conclusion

Hopefully, now that you have learned about state machines you will start using them in your own designs and maybe even use Qt for its built in state machine support.

If you want to learn more about graphically working with state machines in Qt, get a copy of my book Hands-On Embedded Programming with Qt and check out "Designing with State Machines in Chapter 7.  You can find it either on the Packt Website or on Amazon.