View source for Event-driven finite-state machine

{{No footnotes|date=November 2024}}
{{comp-sci-theory-stub}} 

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==

[https://github.com/ntozubod/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==
* [https://github.com/ntozubod/ginr/blob/main/USAGE.md Ginr] (ginr whitepaper and user's guide)
* [https://github.com/jrte/ribose/blob/master/README.md Ribose] (demonstrates using ginr to transduce sequential media)

==Further reading==
*{{cite book | last = Peatman | first = John B. | title = Microcomputer-based Design | year = 1977 | publisher = McGraw-Hill, Inc. | location = New York | isbn = 0-07-049138-0}}
*{{cite book | last = Brookshear | first = J. Glenn | title = Theory of Computation: Formal Languages, Automata, and Complexity | year = 1989 | publisher = Benjamin/Cummings Publish Company, Inc. | location = Redwood City, California | isbn = 0-8053-0143-7}}

{{DEFAULTSORT:Event-Driven Finite State Machine}}
[[Category:Models of computation]]