Community hub
0 subscribers7 pages, 0 posts
Recent from talks
All channels
Be the first to start a discussion here.
Be the first to start a discussion here.
Be the first to start a discussion here.
Be the first to start a discussion here.
Contribute something
Welcome to the community hub built to collect knowledge and have discussions related to Event-driven finite-state machine.
Nothing was collected or created yet.
Event-driven finite-state machine
View on Wikipediafrom Wikipedia
 | This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. (November 2024) |
 | This article's "Same example in Ginr" section contains promotional content. (October 2025) |
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
[edit]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).
/********************************************************************/
#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;
}
}
}
Same example in Ginr
[edit] | This section contains promotional content. (October 2025) |
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 (nil, radio) to set the system into its initial state. Here the input symbols nil, mode, next denote events that drive a transducer with output effectors cd, nextTrack, radio, nextStation. Expressions like this are generally much easier to express and maintain than explicit listings of transitions.
StateMachine = (
(nil, radio)
(
(mode, cd) (next, nextTrack)*
(mode, radio) (next, nextStation)*
)*
(
(mode, cd) (next, nextTrack)*
)?
);
Compilation produces a subsequential (single-valued) binary transducer mapping sequences of events to sequences of effectors that actuate features of the CD/radio device.
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
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
[edit]External links
[edit]Further reading
[edit]- Peatman, John B. (1977). Microcomputer-based Design. New York: McGraw-Hill, Inc. ISBN 0-07-049138-0.
- Brookshear, J. Glenn (1989). Theory of Computation: Formal Languages, Automata, and Complexity. Redwood City, California: Benjamin/Cummings Publish Company, Inc. ISBN 0-8053-0143-7.
Event-driven finite-state machine
View on Grokipediafrom Grokipedia
Fundamentals
Definition
An event-driven finite-state machine is a computational model that describes system behavior through a finite collection of states, with transitions between states triggered exclusively by discrete events rather than continuous signals or elapsed time. This approach enables precise modeling of reactive systems, where the system's response to stimuli—such as user inputs, sensor detections, or messages—determines its evolution, ensuring predictable and modular design in environments demanding immediate reactivity.[5] In contrast to broader reactive computing paradigms, which may involve asynchronous data streams or continuous interactions, event-driven finite-state machines impose a strict finite state space and rely on event-driven transitions to maintain determinism and scalability, particularly in handling concurrency without combinatorial explosion. This emphasis on discreteness facilitates verification and implementation in domains like embedded software and protocol design.[6] Event-driven finite-state machines emerged in the 1970s and 1980s as key tools in the design of concurrent and real-time systems, building on early microprocessor applications for control logic and evolving to address the limitations of unstructured programming in multitasking environments. A pivotal advancement came with David Harel's statecharts in 1987, which influenced event-driven finite-state machine concepts by introducing hierarchical structures to manage complexity in event-responsive behaviors.[7][6] Fundamentally, an event-driven finite-state machine comprises a finite set of states representing possible configurations, events acting as inputs, and deterministic transitions that specify the next state based on the current state and incoming event.[8]Key Components
An event-driven finite-state machine is composed of a finite set of states, which represent the discrete conditions or modes in which the system can operate at any given time. These states encapsulate the system's configuration and behavior, allowing it to model complex processes by partitioning the system's lifecycle into manageable phases. Typically, an event-driven finite-state machine distinguishes between an initial state, which serves as the starting point upon system activation; final states, which denote termination or acceptance conditions; and intermediate states, which handle transient or ongoing operations. This structure ensures that the system remains in exactly one state at any moment, providing a clear boundary for behavioral logic.[9] Events form the stimuli that drive the event-driven finite-state machine's dynamics, consisting of external or internal signals such as user inputs, timeouts, or hardware signals that prompt potential changes in the system's state. In formal terms, events are drawn from a predefined alphabet, enabling the machine to respond reactively to its environment without continuous polling. A key feature is the asynchronous processing of events, often via event queues, allowing non-blocking handling in concurrent environments. For instance, in reactive systems like those modeled by statecharts, events include asynchronous signals from other components, elapsed time conditions, or calls to internal procedures, ensuring the machine processes inputs only when triggered.[10] Transitions define the rules governing how the event-driven finite-state machine moves between states in response to events, incorporating conditional logic to handle real-world variability. Each transition is specified by a source state, a target state, and an associated event. Practical implementations may include optional guards (boolean conditions evaluated on the current state and variables to determine if the transition is enabled) and actions (executable code or output generated upon firing, such as updating variables or sending signals). Guards allow transitions to be context-sensitive—for example, a transition might only occur if a variable exceeds a threshold—while actions enable side effects like logging or interfacing with external systems. These extensions accommodate variables and computations for more expressive behaviors in embedded and reactive systems, though the core model remains classical. Outputs can be state-dependent (Moore machine) or depend on both state and event (Mealy machine).[9] Formally, an event-driven finite-state machine can be represented as a 5-tuple , where is the finite set of states, is the set of events, is the transition function, is the initial state, and is the set of final states. This model captures the reactive essence of the system, where execution begins in and proceeds via event-triggered transitions until reaching a state in .Design Principles
Transition Mechanisms
In event-driven finite-state machines (EFSMs), the transition function defines the core logic for state changes, formally expressed as , where is the set of states, is the set of events, and maps the current state to the next state upon occurrence of event .[1] This function encapsulates design-time rules specifying how events trigger deterministic or conditional shifts, ensuring the system's behavior aligns with specified dynamics without reliance on continuous time inputs.[6] To handle non-determinism, where multiple transitions may be possible from a given state for the same event, EFSMs incorporate guards as Boolean conditions evaluated alongside the event. A transition labeled with event and guard (denoted ) fires only if occurs and evaluates to true, resolving ambiguity by constraining applicability based on system variables or context. Guards enable selective triggering, such as requiring a buffer to be full before processing an input event, thereby modeling conditional dependencies during design.[11] Entry and exit actions provide mechanisms for executing behaviors tied to state occupancy rather than transitions themselves. Upon entering a state, an entry action (e.g., initializing variables or allocating resources) is performed atomically before any internal activities; conversely, an exit action (e.g., releasing resources or logging state departure) executes upon leaving the state, after interrupting ongoing do-activities if present.[11] These actions decouple behavioral side effects from the transition logic, promoting modularity in EFSM specifications. Hierarchical states enhance modularity by nesting substates within superstates, allowing transitions to span multiple levels for refined abstraction. A transition from a substate may target an ancestor superstate, implicitly exiting intermediate states and executing their exit actions en route, or enter a sibling substate within the same superstate boundary.[6] This nesting supports composite behaviors without exploding the flat state space, as seen in designs where a "processing" superstate encompasses idle and busy substates. Conflict resolution in EFSMs addresses scenarios with multiple enabled transitions for an event, using priority schemes to select a unique path. Transitions with greater specificity—such as those originating from deeper hierarchical levels or explicit over default—take precedence, often via static reaction where the system reacts immediately without intermediate steps. For instance, in overlapping orthogonal regions, the transition with the highest scope (encompassing the broadest context) resolves ambiguity, ensuring unambiguous design-time specification.[12]Event Handling
In event-driven finite-state machines (EFSMs), event handling governs the runtime processing of incoming stimuli, ensuring reactive behavior where the system responds promptly to asynchronous inputs while maintaining efficiency through structured mechanisms. Upon arrival, events are buffered and sequenced to prevent overload, then dispatched based on the machine's current state to trigger appropriate transitions, fostering modularity and predictability in complex systems. This process not only handles external triggers but also accommodates internally generated events, allowing for dynamic state evolution without external intervention. Error conditions, such as unhandled events, are managed to preserve system stability, often by deferring or discarding them selectively. Event queueing in EFSMs employs buffering strategies to manage asynchronous events, decoupling their arrival from immediate processing to enhance throughput and fault tolerance. A common approach is first-in-first-out (FIFO) sequencing, where events are enqueued and dequeued in arrival order, as seen in implementations using operating system queues like those in FreeRTOS for embedded applications. For scenarios requiring differentiated responsiveness, priority queues organize events into bands or levels, with higher-priority bands processed before lower ones; within each band, FIFO maintains fairness. For instance, in extended statechart models, banded queues assign priorities (e.g., levels 3, 4, 7) to event types, enabling critical events like timeouts to preempt routine ones while avoiding starvation through intra-band ordering. These mechanisms, such as queue thresholding in staged event-driven architectures, can reject or drop excess events when buffers fill, applying backpressure to upstream components to regulate load. Dispatching integrates the queued events with the EFSM's runtime context, where the current state dictates which potential transitions are evaluated and executed upon event consumption. An event dispatcher typically dequeues the highest-priority event and consults the state-specific transition rules, proposing it for disposition only if compatible with the active configuration. In statechart extensions, this involves a disposition matrix that resolves conflicts by prioritizing based on the current state's hierarchy, ensuring that only valid transitions—such as those matching event guards—are fired. This state-dependent evaluation promotes efficiency, as irrelevant events are filtered early, reducing computational overhead in reactive systems like distributed actors. Internal events in EFSMs arise from state entry, exit, or transition actions, facilitating self-contained behaviors such as self-transitions or event chaining without relying on external inputs. These "soft" events, often generated via timers or completion signals, are enqueued separately from external ones and processed after the primary event chain resolves, enabling modular extensions like timeout handling in idle states. For example, in actor-based models, state actions produce internal messages that update the local state and propagate to neighboring components, supporting chained reactions in graph processing pipelines. This generation mechanism allows EFSMs to model compound behaviors, where an action in one state triggers subsequent internal events for validation or cleanup, enhancing autonomy in event-sourced systems. Error handling addresses unhandled events—those without matching transitions in the current state—through policies that balance robustness and performance. Common strategies include silent discarding, where incompatible events are dropped without state change, or deferral to a later queue band for re-evaluation. In disposition-based frameworks, unhandled events invoke predefined actions like logging for diagnostics or ignoring to maintain forward progress, preventing deadlock in concurrent environments. For instance, malformed or unexpected inputs may trigger error states via internal events, logging details while resetting to a safe configuration, as implemented in protocol stacks using status codes for fault isolation.Comparisons
Versus Traditional Finite-State Machines
Traditional implementations of finite-state machines (FSMs), including those based on the Moore and Mealy models, are typically driven by synchronous inputs or timed sequences, where outputs in Moore machines depend solely on the current state and in Mealy machines on both the state and inputs, without an explicit abstraction for events.[13] These classical models assume a sequential, often polled evaluation of inputs in a deterministic manner, commonly implemented in hardware or software superloops that continuously check conditions.[14] In contrast, event-driven finite-state machines (EFSMs) introduce an explicit event abstraction, decoupling raw inputs from state transitions by treating events as queued objects that encapsulate signals and parameters, enabling asynchronous processing without constant polling.[15] This allows EFSMs to handle non-deterministic inputs more gracefully, as events are dispatched reactively rather than synchronously evaluated at fixed intervals, reducing risks like race conditions in interrupt-heavy environments.[15] EFSMs offer advantages in non-deterministic and interrupt-driven systems, where traditional FSM implementations may undersample asynchronous changes or require heavy synchronization overhead, making EFSMs more suitable for scalable, concurrent scenarios with lower power consumption and easier concurrency management.[16] For instance, a traditional traffic light controller might cycle states based on fixed timers and polled sensor inputs, as in a Moore FSM implementation with timed delays for green (30 seconds) and yellow (5 seconds) phases.[14] In an EFSM version, sensor detections (e.g., pedestrian crossings or emergency vehicles) generate immediate events to trigger state changes, bypassing rigid timing for more responsive behavior.[15]Versus Input-Driven State Machines
Input-driven state machines, prevalent in early embedded software designs, operate by continuously polling input sources such as flags, variables, or hardware registers within a repetitive loop, often implemented using switch-case constructs in a while(1) superloop.[15][17] This polling mechanism checks for changes at fixed intervals, leading to busy-waiting where the processor remains active even when no relevant input occurs, which can introduce inefficiencies in resource utilization.[18] In contrast, event-driven finite-state machines (EFSMs) respond to discrete events—such as interrupts, messages, or callbacks—generated externally and dispatched asynchronously, eliminating the need for constant polling and allowing the system to remain idle until an event triggers a state transition.[15] This approach enhances efficiency in real-time systems by leveraging hardware interrupts or software event queues, thereby reducing CPU overhead and enabling better responsiveness without the deterministic timing issues of polling loops.[16] For instance, in embedded applications, EFSMs integrate seamlessly with real-time operating systems (RTOS) to handle events like sensor triggers or timer expirations through non-blocking mechanisms.[15] Historically, input-driven state machines dominated early embedded code, particularly in bare-metal systems of the 1980s and 1990s, due to their simplicity in resource-constrained environments without sophisticated multitasking support.[17] EFSMs gained prominence in the 1990s alongside the widespread adoption of RTOS, which facilitated event queuing and dispatching, marking a shift toward more scalable, reactive architectures in complex embedded designs.[19] Performance-wise, EFSMs offer significantly lower latency through immediate interrupt handling compared to the delays of periodic polling, critical for time-sensitive applications like automotive controls.[18] Additionally, they achieve significant power savings in low-power devices by allowing the CPU to remain idle until events occur, as opposed to the continuous energy drain from polling, which is particularly beneficial in battery-operated embedded systems.[18][16]Implementations
In General-Purpose Languages
Implementing event-driven finite-state machines (EFSMs) in general-purpose languages like C relies on fundamental programming constructs to model states, events, and transitions without specialized libraries. States are typically represented using enumerations (enums) to define a discrete set of possible values, ensuring type safety and clarity in code. For instance, an enum can list states such asIDLE, SELECTING, and DISPENSING, while structs may encapsulate additional state-specific data like variables or function pointers if needed. Transition logic is commonly handled via switch statements, which evaluate the current state and incoming event to determine the next state and any associated actions. This approach leverages the language's control flow for efficient, readable implementations suitable for embedded or systems programming.[20][21]
The core of an EFSM implementation involves an event loop or dispatcher function that continuously processes events, updating the machine's state accordingly. This dispatcher acts as the main execution thread, polling or waiting for events (e.g., from interrupts, queues, or user inputs) and invoking the appropriate transition handler based on the current state. Events themselves can be represented as enums or simple integers, with the loop using a switch on the current state to route the event to the correct case, where transitions and side effects (like outputting signals) occur. This structure promotes modularity, as each state case can call dedicated handler functions for entry, exit, or event processing. Event queueing may be employed to buffer asynchronous inputs, ensuring orderly processing.[21][15]
A practical example is a simple vending machine EFSM in C, modeling states like idle (waiting for input), selecting (after coin insertion), and dispensing (item delivery). Events include COIN_INSERT and SELECT_ITEM. The implementation uses enums for states and events, a global current state variable, and a switch-based dispatcher. Below is pseudocode adapted for clarity:
c
#include <stdio.h>
// State enum
typedef enum {
IDLE,
SELECTING,
DISPENSING
} State;
// Event enum
typedef enum {
COIN_INSERT,
SELECT_ITEM,
TIMEOUT // e.g., for resetting
} Event;
// Global current state
State current_state = [IDLE](/page/IDLE);
// Transition function (actions and state updates)
State handle_event(Event e) {
switch (current_state) {
case [IDLE](/page/IDLE):
if (e == COIN_INSERT) {
// Action: Enable selection buttons
[printf](/page/Printf)("Selection enabled\n");
return SELECTING;
}
break;
case SELECTING:
if (e == SELECT_ITEM) {
// Action: Dispense item, return change if needed
[printf](/page/Printf)("Item dispensed\n");
return DISPENSING;
} else if (e == TIMEOUT) {
[printf](/page/Printf)("Selection timed out\n");
return [IDLE](/page/IDLE);
}
break;
case DISPENSING:
// Action: Complete dispensing
[printf](/page/Printf)("Dispensing complete\n");
return [IDLE](/page/IDLE);
}
return current_state; // No transition
}
// Main event loop (dispatcher)
int main() {
Event next_event;
while (1) {
// Simulate event acquisition (e.g., from queue or input)
next_event = get_next_event(); // Placeholder for event source
current_state = handle_event(next_event);
}
return 0;
}
#include <stdio.h>
// State enum
typedef enum {
IDLE,
SELECTING,
DISPENSING
} State;
// Event enum
typedef enum {
COIN_INSERT,
SELECT_ITEM,
TIMEOUT // e.g., for resetting
} Event;
// Global current state
State current_state = [IDLE](/page/IDLE);
// Transition function (actions and state updates)
State handle_event(Event e) {
switch (current_state) {
case [IDLE](/page/IDLE):
if (e == COIN_INSERT) {
// Action: Enable selection buttons
[printf](/page/Printf)("Selection enabled\n");
return SELECTING;
}
break;
case SELECTING:
if (e == SELECT_ITEM) {
// Action: Dispense item, return change if needed
[printf](/page/Printf)("Item dispensed\n");
return DISPENSING;
} else if (e == TIMEOUT) {
[printf](/page/Printf)("Selection timed out\n");
return [IDLE](/page/IDLE);
}
break;
case DISPENSING:
// Action: Complete dispensing
[printf](/page/Printf)("Dispensing complete\n");
return [IDLE](/page/IDLE);
}
return current_state; // No transition
}
// Main event loop (dispatcher)
int main() {
Event next_event;
while (1) {
// Simulate event acquisition (e.g., from queue or input)
next_event = get_next_event(); // Placeholder for event source
current_state = handle_event(next_event);
}
return 0;
}
COIN_INSERT to move from IDLE to SELECTING, then SELECT_ITEM to DISPENSING, before returning to IDLE.[21][14]
Challenges in these implementations arise particularly with concurrency, where multiple threads or asynchronous signals can lead to race conditions if events modify shared state unpredictably. In C, managing this often requires message queues to serialize event delivery from threads, preventing direct shared-state access and ensuring thread-safe transitions. Signals, common in POSIX environments, must be carefully integrated to avoid interrupting critical sections, potentially using mutexes or atomic operations for protection. These issues highlight the need for disciplined event sourcing to maintain EFSM integrity in multi-threaded contexts.[22][15]
Specialized Tools and Frameworks
Several specialized tools and frameworks facilitate the design and implementation of event-driven finite-state machines by providing domain-specific languages (DSLs), visual modeling, and runtime environments. These tools automate the generation of boilerplate code, support hierarchical and concurrent states, and integrate with various programming languages, reducing errors in complex systems. The State Machine Compiler (SMC) is a tool that generates state machine code from a textual description in a simple format, supporting event-driven behaviors across languages like C, C++, Java, and Python. Users define states, transitions, and actions in a .sm file using a syntax that specifies the current state, event, and next state with optional guards and actions. For example:: IDLE
COIN_INSERT -> SELECTING { enable_selection(); }
: SELECTING
SELECT_ITEM -> DISPENSING { dispense_item(); }
TIMEOUT -> IDLE { disable_selection(); }
: DISPENSING
COMPLETE -> IDLE { complete_dispensing(); }
: IDLE
COIN_INSERT -> SELECTING { enable_selection(); }
: SELECTING
SELECT_ITEM -> DISPENSING { dispense_item(); }
TIMEOUT -> IDLE { disable_selection(); }
: DISPENSING
COMPLETE -> IDLE { complete_dispensing(); }