Event-driven finite-state machine

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.

The author of StateCHARTS uses the term event driven finite state machine to describe machines where any incoming input has to be consumed immediately, i.e. the FSM has to perform a transition or input action otherwise the input disappears.

In contrast to the StateCHART virtual finite state machine (VFSM) technology, the application of event driven FSM in complex systems leads to the state explosion problem, as each truly required state path must be repeated for all possible input values. Event driven FSM can be implemented with a state transition table as is often done for parser applications.

A significant reduction in complexity can be achieved by utilizing hierarchy a la hierarchical state machines (HSMs). The use of hierarchy eliminates the "state explosion" problem by allowing a single transition from multiple related states, through state nesting. A more rigorous definition of hierarchical state machines that includes an example can be found at http://www.quantum-leaps.com/resources/glossary.htm#HSM.