In computation, a finite-state machine (FSM) is event driven if the transition from one state to another is triggered by an event or a message. 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, a telecommunication protocol is most of the time implemented as an event-driven finite-state machine.
Example in C
This code describes the state machine for a very basic car radio system. It is basically an infinite loop that reads incoming events. The state machine is only 2 states: radio mode, or CD mode. The event is either a mode change from radio to cd back and forth, or a go to next (next preset for radio or next track for CD).
<syntaxhighlight lang="c">
/********************************************************************/
- include <stdio.h>
/********************************************************************/
typedef enum {
ST_RADIO,
ST_CD
} STATES;
typedef enum {
EVT_MODE,
EVT_NEXT
} EVENTS;
EVENTS readEventFromMessageQueue(void);
/********************************************************************/
int main(void)
{
/* Default state is radio */
STATES state = ST_RADIO;
int stationNumber = 0;
int trackNumber = 0;
/* Infinite loop */
while (1)
{
/* Read the next incoming event. Usually this is a blocking function. */
EVENTS event = readEventFromMessageQueue();
/* Switch the state and the event to execute the right transition. */
switch (state)
{
case ST_RADIO:
switch (event)
{
case EVT_MODE:
/* Change the state */
state = ST_CD;
break;
case EVT_NEXT:
/* Increase the station number */
stationNumber++;
break;
}
break;
case ST_CD:
switch (event)
{
case EVT_MODE:
/* Change the state */
state = ST_RADIO;
break;
case EVT_NEXT:
/* Go to the next track */
trackNumber++;
break;
}
break;
}
}
}
</syntaxhighlight>
Same example in Ginr
Ginr is an industrial-strength compiler producing multitape finite state automata from rational patterns, functions and relations expressed in semiring algebraic terms. The example below shows a binary rational function equivalent to the above example, with an additional transition <em>(nil, radio)</em> to set the system into its initial state. Here the input symbols <em>nil, mode, next</em> denote events that drive a transducer with output effectors <em>cd, nextTrack, radio, nextStation</em>. Expressions like this are generally much easier to express and maintain than explicit listings of transitions.
<pre>
StateMachine = (
(nil, radio)
(
(mode, cd) (next, nextTrack)*
(mode, radio) (next, nextStation)*
)*
(
(mode, cd) (next, nextTrack)*
)?
);
</pre>
Compilation produces a subsequential (single-valued) binary transducer mapping sequences of events to sequences of effectors that actuate features of the CD/radio device.
<pre>
StateMachine:prsseq;
(START) nil [ radio ] 1
1 mode [ cd ] 2
2 mode [ radio ] 3
2 next [ nextTrack ] 2
3 mode [ cd ] 2
3 next [ nextStation ] 3
</pre>
Modelling discrete systems in this manner obtains a clean separation of syntax (acceptable ordering of events) and semantics (effector implementation). The syntactic order of events and their extension into the semantic domain is expressed in a symbolic (semiring) domain where they can be manipulated algebraically while semantics are expressed in a procedural programming language as simple effector functions, free from syntactic concerns. The rational expressions provide concise holistic maps of the protocols that effect system governance. The compiled automata are post-processed to obtain efficient controllers for run-time deployment.
See also
- Finite-state machine
- Specification and Description Language
External links
- Ginr (ginr whitepaper and user's guide)
- Ribose (demonstrates using ginr to transduce sequential media)