Event-driven finite state machine

In computation, a finite state machine (FSM) is event driven if the creator of the FSM intends to think of the machine as consuming events or messages. This is in contrast to the parsing-theory origins of the term finite-state machine where the machine is described as consuming characters or tokens.

Often these machines are implemented as threads or processes communicating with one another as part of a larger application. For example, an individual car in a traffic simulation might be implemented as an event-driven finite-state machine.

This is a common and useful idiom, though not as precisely defined and theoretically grounded as the application of finite state machines to parsing. By abuse of terminology, programmers may refer to code created while thinking of this idiom as a finite state machine even if the space required for the state grows with the size of the input.

Example in C

This code describes the state machine for a British traffic light, which follows the pattern; red -> red+yellow -> green -> yellow -> red.

/********************************************************************/
#include

/********************************************************************/typedef enum { STATE_INIT, STATE_RED, STATE_RED_AND_YELLOW, STATE_GREEN, STATE_YELLOW, STATE_FINISHED} STATES;

#define OPERATION_DONE 1

void state_machine( int *, int );void state_red( int * );void state_red_and_yellow( int * );void state_green( int * );void state_yellow( int * );

#define state_init state_red

/********************************************************************/int main(){ int state = STATE_INIT, operation;

while( state != STATE_FINISHED ) { switch( state ) { case STATE_INIT: state_init( &operation ); printf("i"); break;

case STATE_RED: state_red( &operation ); printf("r"); break;

case STATE_RED_AND_YELLOW: state_red_and_yellow( &operation ); printf("o"); break;

case STATE_GREEN: state_green( &operation ); printf("g"); break;

case STATE_YELLOW: state_yellow( &operation ); printf("y"); break; }

state_machine( &state, operation ); }

return;}

/********************************************************************/void state_machine( int *state, int operation ){ switch( *state ) { case STATE_INIT: switch( operation ) { case OPERATION_DONE: *state = STATE_RED; break; } break;

case STATE_RED: switch( operation ) { case OPERATION_DONE: *state = STATE_RED_AND_YELLOW; break; } break;

case STATE_RED_AND_YELLOW: switch( operation ) { case OPERATION_DONE: *state = STATE_GREEN; break; } break;

case STATE_GREEN: switch( operation ) { case OPERATION_DONE: *state = STATE_YELLOW; break; } break;

case STATE_YELLOW: switch( operation ) { case OPERATION_DONE: *state = STATE_RED; break; } break; }

return;}

/********************************************************************/void state_red( int *operation ){ // change traffic light to red only // wait for 30 seconds to let other traffic through

*operation = OPERATION_DONE;

return;}

/********************************************************************/void state_red_and_yellow( int *operation ){ // change traffic light to red and yellow // wait for 5 seconds to let people get ready

*operation = OPERATION_DONE;

return;}

/********************************************************************/void state_green( int *operation ){ // change traffic light to green only // then wait for 30 seconds to let some traffic through

*operation = OPERATION_DONE;

return;}

/********************************************************************/void state_yellow( int *operation ){ // change traffic light to yellow only // then wait for 5 seconds to let traffic know we're going to go red

*operation = OPERATION_DONE;

return;}

ee also

* Finite state machine