How to use state machines for your modeling (Part 4): The state machine as a table

In the first parts of our series "How to use state machines for your modeling", we have looked at the basics of state machines and graphical modelling (see part 1 and part 2) and discovered the implementation by means of a switch statement.

Now let’s take a look at another approach, which is popular in automata theory: using state transition tables for the specification of state machines. The initial and target states, as well as the events that lead to a transition from the initial to a target state, are listed in a table that the implementation refers to repeatedly.

One-dimensional state transition tables

A one-dimensional state transition table defines one state transition per line. In the simplest case the table contains two columns: one contains all the initial states, the others the respective assigned states.

For a traffic light control it looks like this:

The reality is, of course, more complex: a traffic light should not be rushing through its states in a fraction of a second. Instead it should remain in the current state for a specific time, then change to the next state. This behaviour can be approximated by a slow clock of, say, ten seconds. The state machine looks at the table at every clock pulse, checks what the current state is and changes to the following state.

However, the result would still be very unsatisfactory, because the yellow phases would be much too long and the red and green phases would be much too short. We need different durations in the individual phases. This can be achieved with time-controlled events, as already described. The change from the state Red to Red-Yellow, for example, takes place only after the occurrence of the event 20 s passed.

In single-dimensional state transition tables each event is usually assigned its own table column. Those state transitions – represented by the rows of the table – that should only take place when the event is present contain a checkmark in the corresponding cell:

The first line describes the state transition from Red to Red-Yellow. Since a check mark has been placed in the event column 20 s passed, the transition takes place only after this event has arrived. The events 3 s passed and 30 s passed here are irrelevant, so the check mark is omitted.

Controlling a blind with the status transition table

The state transition table for the blind control system looks like this:

The state transition table in the source code

This table can easily be converted into the source code of the desired programming language. We've already seen examples in Java, so here's something for C programmers:

#include 
#include 

enum states {
    INITIAL, IDLE, MOVING_UP, MOVING_DOWN
};

enum columns {
    SOURCE_STATE, USER_UP, USER_DOWN, POSSENSOR_UPPER_POSITION, POSSENSOR_LOWER_POSITION, TARGET_STATE
};

#define ROWS 7
#define COLS 6

int state_table[ROWS][COLS] = {

    /* source,     up,    down,  upper, lower, target */
    
    { INITIAL,     false, false, false, false, IDLE },
    { IDLE,        true,  false, false, false, MOVING_UP },
    { IDLE,        false, true,  false, false, MOVING_DOWN },
    { MOVING_UP,   false, true,  false, false, IDLE },
    { MOVING_UP,   false, false, true,  false, IDLE },
    { MOVING_DOWN, true,  false, false, false, IDLE },
    { MOVING_DOWN, false, false, false, true,  IDLE }
};

The enum states contains symbolic names of the states, simplifying the creation of the table state_table. The enum columns assigns symbolic names to the column numbers. For example, the sample program below does not need to address the columns with the initial and target states, with their absolute indexes 0 and 5, but uses the symbolic names SOURCE_STATE and TARGET_STATE. The symbolic names of the events are not needed in the sample program, but they are helpful for manual maintenance of the state transition table.

The table state_table specifies the state machine purely declaratively. If the machine changes, only adjustments to the table are necessary. This is clear as long as the number of states and events is small. If the number should increase, however, clarity and maintainability fall by the wayside. After all, the actual program code remains unchanged – an advantage because changes are simpler and less error-prone.

We have already looked at the first part of the example implementation in C. The function main is shown below. The program asks for the number of the next event, which the user enters via the default input. The event numbers correspond to the position of the event in columns, i.e. USER_UP = 1, USER_DOWN = 2 and so on. The machine then consults the table. If it finds a transition that triggers the entered event, the program informs the user of the row and column in the table and returns the number of the new state. These numbers correspond to the respective position in the enumeration states.

int main(int argc, char** argv) {

    int activeState = INITIAL;
    int event = -1;
    
    while (true) {
    
        int row, col;
    
        bool checkRows = true, checkCols;
    
        printf("Active state: %d\n", activeState);
        printf("Event: %d\n", event);
    
        /* Look for a row with the active state in the SOURCE_STATE column: */
        for (row = 0; checkRows && row < ROWS; row++) {
    
           checkCols = true;
    
            if (activeState == state_table[row][SOURCE_STATE]) {
                /* Found a row matching the active state. */
                /* Now check the columns for events triggering this transition: */
    
                for (col = SOURCE_STATE + 1; checkCols && col < TARGET_STATE; col++) {
    
                    if (state_table[row][col]) {
                        /* Found one. The current event must match this column
                         * to trigger the transition. */
    
                       if (event == col) {
                            /* The event matches. Let's do the transition: */
    
                            printf("Active state and event matching row %d, column %d.\n", row, col);
                            printf("Transitioning to target state %d\n", activeState);
    
                            activeState = state_table[row][TARGET_STATE];
    
                            /* Stop checking any further rows and columns: */
                            checkRows = checkCols = false;
    
                        } else {
                            /* The event does not match, so this transitions won't be triggered.
                             * We do not need to check any remaining columns: */
    
                            checkCols = false;
    
                        }
                    }
                }
    
                if (checkCols) {
    
                    /* At this point, we have checked all columns, but none of them requires an event
                     * for this transition. So we can do the transition in any case: */
    
                    printf("Transitioning without any event to target state %d\n", activeState);
                    
                    activeState = state_table[row][TARGET_STATE];
                    checkRows = false;
                }
            }
        }
    
        printf("Active state: %d\n\n", activeState);
        printf("Please enter event number!\n");
    
        scanf("%d", &event);
    }
}

Attentive readers may notice that this implementation does not use a fixed clock, but is purely event-driven.

Conditions and actions

Unlike this example, transitions usually depend not only on events, but also on additional conditions (guard conditions). This means that a transition "pulls" not only if the right event is present, but also only if the guard condition is fulfilled. In the implementation, a transition is represented by a function that checks the condition.

The state transition table therefore does not encode any truth values, but instead has pointers to the relevant evaluation functions. In object-oriented languages this can be an object that contains the evaluation function. If the value is zero in a table cell, this is equivalent to false, that is, there is no transition for this combination of state and event. However, if the table contains a nonzero value, this value is the pointer to an evaluation function. This is true (i.e. non-zero) first; the transition is thus a candidate for execution in principle. The implementation now calls the function. This checks the guard condition and, based on its return value, determines whether or not the state machine should actually perform the transition.

Transitions and states can be linked to actions. Actions can also be left to the functions to which the state transition table refers. Such a function therefore not only checks the guard condition, but also activates the following state if the condition is fulfilled.

Concepts such as orthogonality, compound states or history states are difficult to implement with a table. In theory there is an equivalent representation for each of these constructs as a flat state machine, but in practice the state space explodes very quickly. For example, to map orthogonal regions in a flat automatic state machine there must be a separate state for each permutation of the active states in the orthogonal regions. The number of these states is given by the cross-product of the states in the orthogonal regions. In two orthogonal regions, each with three states, nine flat states may still be possible, but there are 810 flat states in ten orthogonal regions each with eight states. That is more than a billion.

Two-dimensional state transition tables

Two-dimensional transition tables are generally more compact than one-dimensional tables, because a single row is sufficient per output state. The respective target state is noted in the cells in which output state lines intersect with event columns. In the following table the event User.down (third column) in the Idle state (second row) leads to the target state Moving down.

The implementation basically looks the same as for one-dimensional tables. A truth value is no longer sufficient for the table cells; instead the respective target state must be encoded. If we want to consider the guard conditions and actions associated with transitions, we need a pointer to a function that corresponds to the transition and implicitly contains the subsequent state. These are as a rule quite different functions for the same subsequent state.

In the following parts of this series, we will learn about the object-oriented “State” software design pattern. We will compare the three implementation approaches – and see how automatic code generation with YAKINDU Statechart Tools can help save the overall implementation effort.

To read the whole “How to use state machines for your modeling” series, download our whitepaper for free.