How to code a Finite State Machine

This page wants to show an easy procedure to overcome the pain of implementing in whatever language you want a Finite State Machine.

Simple example

Let's take a simple state machine:

The state machine can be always represented using a matrix form:

origin\destination	state 0	state 1
state 0	--	transition 1 = f01()
state 1	transition 2 = f10()	--

 

A state machine has always a set of inputs and outputs. These includes the variable that are used for checking the transitions and the variables changes in the various states.

xxxxxxxxxx
var inputs = {
    switch_value : ...
}

the state machine function has to keep in memory always the last status.

!!! At the first FSM function call the last status is the default value (in the above scheme is state 0)

Since we defined the state machine in matrix form we can say that the last_status corresponds to the matrix row index.

xxxxxxxxxx
var last_status = 0;

For the sake of convenience the last_status can be integrated in the inputs.

xxxxxxxxxx
var inputs = {
    switch_value : ...,
    last_status : 0
}

Since we change the state we have inside the outputs also the new state:

xxxxxxxxxx
var outputs = {
    output_value : null,
    new_status : null
}

A set of parameters could be also present:

xxxxxxxxxx
var parameters = {
    value_threshold : 0.5
}

Each state acts on the outputs. For example:

• State 0 : output_value = 0;
• State 1 : output_value = 1;

For each state we can define the function associated that is executed when we enter the state:

xxxxxxxxxx
function f0(){
    output_value = 0;
}
​
function f1(){
    output_value = 1;
}

For associating the function to the state we can build an array of function references that matches the state "column" array:

xxxxxxxxxx
var statefun_array = [fA,fB];

Let's define the transition function. These function shall return always a bool in order to describe if the transition is activated or not. For example:

• transition 1 : is a function of switch_value :

  xxxxxxxxxx
  function f01(switch_value){
      return switch_value > parameters.value_threshold;
  }
  

• transition 2 : is a function similar to the previous:

  xxxxxxxxxx
  function f10(switch_value){
      return switch_value <= parameters.value_threshold;
  }
  

 

Now we have to associate each transition to the states. We do by following the matrix we defined before:

xxxxxxxxxx
var transition_matrix = [[null  ,   f01 ],
                         [f10   ,   null]];

Now we can write the state machine main function:

xxxxxxxxxx
function fsm_step(inputs,parameters,transition_matrix,statefun_array){
    var outputs = ... ;
    
    var num_states = transition_matrix[inputs.last_status].length;
    
    for (let i = 0; i < num_states; i++) {
        if(transition_matrix[inputs.last_status][i]!==null){
            if (transition_matrix[inputs.last_status][i](inputs.switch_value)){
                statefun_array[i](); //evaluate function at state entrance
                outputs.new_status = i;
            }
        }
        
    }
    return outputs;
}

 

To run the state machine :

xxxxxxxxxx
// --------------------------------------------------
// fsm execeution
​
/*someone changes the inputs. for example trought a GUI 
$('button').click(function(){ 
    inputs.switch_value += 0.1;});
*/
​
fsm_execute();
​
// --------------------------------------------------
// variable declaration
var inputs = {
    switch_value : 0.2,
    last_status : 0
}
var parameters = {
    value_threshold : 0.5
}
// it is a good practice to always initialize the output
var outputs = {
    output_value : 0,
    new_status : 0
}
var transition_matrix = [[null  ,   f01 ],
                         [f10   ,   null]];
var statefun_array = [f0,f1];
​
// --------------------------------------------------
// functions definition
​
async function fsm_execute(){
    while(true){
        outputs = fsm_step(inputs,parameters,transition_matrix,statefun_array);
        inputs.last_status = outputs.new_status;
    }
}
​
function fsm_step(inputs,parameters,transition_matrix,statefun_array){
    var outputs = ... ;
    
    var num_states = transition_matrix[inputs.last_status].length;
    
    for (let i = 0; i < num_states; i++) {
        if(transition_matrix[inputs.last_status][i]!==null){
            if (transition_matrix[inputs.last_status][i](inputs.switch_value)){
                statefun_array[i](); //evaluate function at state entrance
                outputs.new_status = i;
            }
        }
        
    }
    return outputs;
}
​
function f0(){
    output_value = 0;
}
​
function f1(){
    output_value = 1;
}
​
function f10(switch_value){
    return switch_value <= parameters.value_threshold;
}
​
function f01(switch_value){
    return switch_value > parameters.value_threshold;
}

 

Why should we bother to do all of this?

In the above example an if else would have been the best solution but when the problem scales up, a spaghetti code made of if and switch instruction is not desirable.

If we take for example this 10 state FSM, in which every state is connected to the others:

 

This FSM can be easily described with the state matric form:

xxxxxxxxxx
var transition_matrix = [[null,f01,f02,f03,f04,f05,f06,f07,f08,f09],
                        [f10,null,f12,f13,f14,f15,f16,f17,f18,f19],
                        [f20,f21,null,f23,f24,f25,f26,f27,f28,f29],
                        [f30,f31,f32,null,f34,f35,f36,f37,f38,f39],
                        [f40,f41,f42,f43,null,f45,f46,f47,f48,f49],
                        [f50,f51,f52,f53,f54,null,f56,f57,f58,f59],
                        [f60,f61,f62,f63,f64,f65,null,f67,f68,f69],
                        [f70,f71,f72,f73,f74,f75,f76,null,f78,f79],
                        [f80,f81,f82,f83,f84,f85,f86,f87,null,f89],
                        [f90,f91,f92,f93,f94,f95,f96,f97,f98,null]];
var statefun_array = [f0,f1,f2,f3,f4,f5,f6,f7,f8,f9];

And by using the same fsm_step and fsm_execute() , with appropriate inputs,outputs and parameters and all the function defined; the state machine is implemented without caring to handle branches.

Final considerations

This is a simplified implementation model of a FSM. But can be extended.

For example if we need timers in states an additional matrix that saves the current_time for each evaluated state is needed in order to compare the elapsed time from the state activation and the running time for comparisons.