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.

/********************************************************************/
#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


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Finite-state machine — State machine redirects here. For infinite state machines, see State transition system. For fault tolerance methodology, see State machine replication. SFSM redirects here. For the Italian railway company, see Circumvesuviana. A finite state… …   Wikipedia

  • Finite state machine — A finite state machine (FSM) or finite state automaton (plural: automata ) or simply a state machine, is a model of behavior composed of a finite number of states, transitions between those states, and actions. A finite state machine is an… …   Wikipedia

  • Event-driven programming — Programming paradigms Agent oriented Automata based Component based Flow based Pipelined Concatenative Concurrent computin …   Wikipedia

  • State diagram — State diagrams is a diagram used in the field of computer science, representing the behavior of a system, which is composed of a finite number of states. There are many forms of state diagrams, which differ slightly and have different semantics.… …   Wikipedia

  • X-machine — The X machine ( XM ) is a theoretical model of computation introduced by Samuel Eilenberg in 1974.S. Eilenberg (1974) Automata, Languages and Machines, Vol. A . Academic Press, London.] The X in X machine represents the fundamental data type on… …   Wikipedia

  • Software development process — Activities and steps Requirements Specification …   Wikipedia

  • Loop-switch sequence — A loop switch sequence is a specific derivative of the spaghetti code programming antipattern where a clear set of steps is implemented as a byzantine switch within a loop. Also known as The FOR CASE paradigm… …   Wikipedia

  • Control table — This simple control table directs program flow according to the value of the single input variable. Each table entry holds a possible input value to be tested for equality (implied) and a relevant subroutine to perform in the action column. The… …   Wikipedia

  • Switch-technology — is a technology for automata based programming support. It was proposed by Anatoly Shalyto in 1991. It involves software specification, design, implementation, debugging, documentation and maintenance. The term “automata based programming” is… …   Wikipedia

  • Perl Object Environment — For the Mach variant, see Mach kernel The Perl Object Environment or POE is a library of Perl modules written in the Perl programming language by Rocco Caputo et alia. From CPAN:: POE originally was developed as the core of a persistent object… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”