Event-driven_finite_state_machine

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.

/********************************************************************/

  1. include

/********************************************************************/ typedef enum {

       STATE_INIT,
       STATE_RED, STATE_RED_AND_YELLOW, STATE_GREEN, STATE_YELLOW,
       STATE_FINISHED
} STATES;

  1. 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 * );

  1. 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;
}

See also

Search another word or see Event-driven_finite_state_machineon Dictionary | Thesaurus |Spanish
Copyright © 2014 Dictionary.com, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature
FAVORITES
RECENT

;