Finite-state machine
A finite-state machine (FSM), also known as a finite automaton, is an abstract computational model consisting of a finite set of states, an input alphabet, a transition function that maps states and inputs to next states, a start state, and a set of accepting states.[1] It processes input strings sequentially, changing states based on each symbol, and accepts the string if it ends in an accepting state, thereby recognizing languages in the Chomsky hierarchy's regular class.[2] This model captures systems with limited memory, where behavior depends only on the current state and input, without retaining unbounded history.[3] The origins of finite-state machines trace back to early 20th-century efforts in modeling neural activity and logical computation. In 1943, Warren McCulloch and Walter Pitts proposed finite automata as a simplified model of neural networks in their paper "A Logical Calculus of the Ideas Immanent in Nervous Activity," laying foundational work for cybernetics and automata theory.[3] The concept was formalized in computer science during the 1950s, with George H. Mealy and Edward F. Moore independently developing output-producing variants in 1955–1956, known as Mealy and Moore machines, which extend basic FSMs to produce outputs alongside state transitions.[3] Michael O. Rabin and Dana Scott provided a rigorous mathematical framework in 1959, proving the equivalence between deterministic finite automata and nondeterministic ones, earning them the 1976 Turing Award for contributions to automata theory.[1] Finite-state machines come in several variants tailored to specific needs. Deterministic finite automata (DFAs) have a unique transition for each state-input pair, ensuring predictable behavior, while nondeterministic finite automata (NFAs) allow multiple or epsilon (no-input) transitions, offering more concise representations but equivalent computational power to DFAs via subset construction.[4] Transducer variants like Mealy machines generate outputs on transitions, and Moore machines on states, enabling modeling of reactive systems.[3] FSMs underpin regular expressions, as shown by Stephen Kleene in 1956, linking them to pattern matching in compilers and lexical analyzers.[1] In practice, finite-state machines are fundamental to computer science and engineering, modeling everything from simple protocols and vending machines to complex hardware controllers and software parsers.[5] They enable efficient design of digital circuits via state minimization techniques, such as those from the Myhill-Nerode theorem (1957–1958), which equates language distinguishability to state count.[1] Despite their simplicity, FSMs form the basis for more powerful models like pushdown automata, highlighting their role in the hierarchy of computational complexity.[3]Introduction
Definition and Motivation
A finite-state machine is an abstract computational model that represents systems capable of exhibiting sequential behavior through a limited set of conditions known as states. At any given moment, the machine resides in exactly one state, which encapsulates the relevant history of prior inputs, and transitions to another state based on the current input. This structure allows the machine to produce outputs dependent on both the current state and input, providing a framework for modeling processes with finite memory where the system's response to future inputs is determined solely by its present condition rather than an unlimited record of the past.[6] The concept traces back to Warren McCulloch and Walter Pitts' 1943 model of neural activity, with significant formalization in the 1950s as part of early efforts in automata theory to model digital circuits and recognize patterns in sequences, such as those encountered in language processing.[7][6] Early foundations were laid by Warren McCulloch and Walter Pitts in 1943, who modeled neural activity using finite automata in their paper "A Logical Calculus of the Ideas Immanent in Nervous Activity," laying foundational work for cybernetics and automata theory.[3] Stephen Kleene's 1956 work formalized finite automata, building on McCulloch and Pitts' models, and introduced regular expressions as a means to represent events in nerve nets, linking them to the computational capabilities of simple neural models and laying the groundwork for understanding sequential logic in hardware design. Building on this, Michael Rabin and Dana Scott's 1959 paper formalized finite automata for classifying input tapes and solving decision problems, emphasizing their role in theoretical computer science and circuit synthesis.[8][7][6] Key developments in automata theory during the 1950s and 1960s further solidified the finite-state machine's foundations, particularly through its connection to regular languages—the class of patterns recognizable by such machines. Kleene's introduction of regular expressions in his 1956 paper provided an algebraic notation for describing these languages, enabling precise specifications of state transitions and influencing compiler design and text processing. This era's advancements highlighted the model's utility in abstracting real-world systems like communication protocols and control devices, where exhaustive memory is neither necessary nor feasible.[8] The emphasis on finiteness stems from the model's inherent limitation to a fixed number of states, which bounds the memory and computational power compared to universal models like the Turing machine. Unlike Turing machines, which simulate arbitrary computation via an infinite tape for unbounded storage, finite-state machines are constrained to recognize only regular languages and cannot handle computations requiring indefinite memory, such as those involving nested structures or recursion. This restriction makes them ideal for efficient, predictable implementations in resource-limited environments like embedded systems.[3]Turnstile Example
A coin-operated turnstile provides a classic illustration of a finite-state machine in operation, modeling access control in environments such as subways or amusement parks. The turnstile begins in a locked state, preventing passage until a valid input is received. Inserting a coin unlocks the mechanism, allowing a user to push through and advance to the next position, after which it relocks to require another payment for subsequent entries. This setup demonstrates how the machine's behavior depends on its current state and incoming events, ensuring controlled and predictable responses.[9][10] The turnstile FSM features two primary states: locked, where entry is barred, and unlocked, where passage is permitted. The inputs consist of two events: coin, representing payment insertion, and push, simulating the physical force to rotate the arms. Outputs are implicit and state-dependent; in the locked state, no passage occurs, while in the unlocked state, the turnstile rotates to allow one person through, effectively granting access. These elements capture the machine's reactive nature without explicit signaling beyond mechanical feedback.[9][11] The transitions define how inputs alter states, with invalid inputs typically resulting in no change to maintain security. A coin input in the locked state triggers a transition to unlocked, enabling entry. Conversely, a push input in the unlocked state returns it to locked after allowing passage. If a push occurs in the locked state, the machine remains locked, ignoring the attempt. A coin input in the unlocked state also leaves it unchanged, as payment is unnecessary post-unlock. These rules ensure the FSM only advances on valid sequences, rejecting unauthorized actions.[9][10] To handle error conditions, such as repeated invalid pushes or forced entry attempts, the model can be extended with a jammed or violation state for fault tolerance. In this augmented FSM, abnormal events like pushing a locked turnstile or excessive force trigger a transition to the violation state, where an alarm activates and the mechanism halts. Recovery occurs via a reset event, returning to the locked state and deactivating the alarm, thus incorporating error handling without disrupting the core logic.[11] The following table summarizes the transitions for the basic turnstile FSM:| Current State | Input | Next State | Action/Output |
|---|---|---|---|
| Locked | Coin | Unlocked | Unlock turnstile |
| Locked | Push | Locked | No action (ignore) |
| Unlocked | Push | Locked | Allow passage, relock |
| Unlocked | Coin | Unlocked | No action (ignore) |
Fundamental Concepts
States, Inputs, and Outputs
A finite-state machine (FSM) consists of a finite set of states, denoted as Q, which represent the distinct conditions or modes in which the machine can exist at any given time. Exactly one state is active at any moment, capturing the system's configuration or "memory" of past inputs.[12] Among these, there is a designated initial state q_0 \in Q, from which the machine begins operation upon receiving its first input.[13] For FSMs functioning as acceptors or recognizers, a subset F \subseteq Q identifies the accepting states, where the machine halts after processing an input string if it determines the input is valid according to the defined language.[13] The inputs to an FSM are drawn from a finite input alphabet \Sigma, a set of symbols or events that can trigger changes in the machine's behavior. These inputs serve as the stimuli processed sequentially, with each symbol representing a discrete event or signal that the machine responds to.[12] The term "event" is often used more broadly to encompass any input that causes a state change, including external signals in reactive systems.[14] Synonymous terminology includes "symbols" for individual elements of \Sigma and "conditions" interchangeably with states in descriptive contexts.[12] Outputs are relevant primarily in transducer models of FSMs, where the machine not only changes states but also produces responses from an output alphabet \Gamma. In the Mealy model, outputs are generated as a total function \lambda: Q \times \Sigma \to \Gamma, depending on both the current state and the input, allowing immediate reaction during transitions.[15] This approach, introduced by George H. Mealy, enables outputs to vary dynamically with incoming stimuli.[16] Conversely, in the Moore model, outputs are determined solely by the current state via a total function \lambda: Q \to \Gamma, producing consistent responses for each state regardless of the triggering input.[17] This model, proposed by Edward F. Moore, simplifies output logic by associating it directly with states. Some FSM designs distinguish active states, where outputs or actions occur, from idle states, in which the machine awaits input without generating responses.[18] For illustration, consider a turnstile FSM with states "locked" and "unlocked," where coin inputs from \Sigma = \{ \text{[coin](/page/Coin)}, \text{push} \} drive transitions, and outputs indicate access granted or denied.[13]Transitions and Events
In finite-state machines (FSMs), transitions define the dynamic behavior by specifying how the machine moves from one state to another in response to inputs. A transition is a mapping that, given the current state and an input, determines the next state and may also produce an output.[18] This mechanism ensures that the FSM evolves predictably based on its configuration, with transitions often triggered synchronously at clock edges in hardware implementations.[18] In event-driven or reactive systems, transitions are initiated by events, which serve as the inputs prompting state changes. Events can include signals, user actions, or environmental stimuli, and the FSM responds by firing a valid transition if the event is applicable to the current state; otherwise, the event is typically ignored to maintain stability.[19] For instance, in a turnstile system, a "coin" event in the locked state triggers a transition to the unlocked state, while a "push" event in the same state is ignored, preventing unauthorized passage without altering the state.[11] Nondeterminism introduces the possibility of multiple transitions from the same state for a given input, allowing the FSM to branch to several potential next states, which models uncertainty or parallelism in computation.[20] This contrasts with deterministic FSMs, where each input uniquely determines the next state, and is explored further in classifications of FSM types. Sequences of transitions form paths through the state space, enabling complex behaviors such as cycles, where the machine loops back to a previous state to repeat actions. In the turnstile example, a cycle emerges from the unlocked state via a "push" event back to locked, allowing repeated use after payment and modeling ongoing operation.[11] These paths capture the FSM's response to input sequences, ensuring consistent handling of repetitive or iterative scenarios.[18] Dead states act as sinks in the FSM, representing error conditions where no further valid transitions are possible, trapping the machine indefinitely regardless of subsequent inputs. They are commonly used for error handling, such as in protocol implementations where invalid sequences lead to a fault state requiring external reset.[21] In design, dead states help isolate failures without disrupting the overall model.[18]Mathematical Model
Formal Components
A finite-state machine, in its basic form as an acceptor or recognizer, is formally defined as a quintuple M = (Q, \Sigma, \delta, q_0, F), where Q is a finite set of states, \Sigma is a finite input alphabet, \delta: Q \times \Sigma \to Q is the transition function that maps a current state and an input symbol to a next state, q_0 \in Q is the initial state, and F \subseteq Q is the set of accepting states.[22][23] This structure assumes that both Q and \Sigma are finite, ensuring the machine's computational resources remain bounded, and that \delta is a total function, defined for every pair in Q \times \Sigma.[22] For machines that produce outputs, known as finite-state transducers, the basic tuple is extended with a finite output alphabet \Gamma and an output function \lambda.[24] In a Moore machine, outputs depend solely on the current state, with \lambda: Q \to \Gamma; the full tuple is thus (Q, \Sigma, \Gamma, \delta, q_0, \lambda), where accepting states F may be omitted if the machine is not used as an acceptor.[24] This model ensures that the output is determined immediately upon entering a state, independent of the triggering input.[24] In contrast, a Mealy machine associates outputs with transitions, so \lambda: Q \times \Sigma \to \Gamma; the tuple becomes (Q, \Sigma, \Gamma, \delta, q_0, \lambda), or equivalently, the transition function can incorporate outputs as \delta: Q \times \Sigma \to Q \times \Gamma.[24] Here, the output is produced based on both the current state and the input symbol, allowing for more immediate response to inputs but potentially leading to different output timing compared to Moore machines.[24] As with the basic FSM, finiteness of Q, \Sigma, and \Gamma is required, and functions are total for completeness.[24]Transition Function and Semantics
The transition function, denoted as \delta, is a central component of a finite-state machine (FSM) that specifies how the machine changes states in response to inputs. For a deterministic FSM (DFA), \delta is a total function \delta: Q \times \Sigma \to Q, mapping each pair of a current state q \in Q and an input symbol \sigma \in \Sigma to a unique next state in Q.[25] In a nondeterministic FSM (NFA), \delta is a partial function \delta: Q \times \Sigma \to 2^Q, where $2^Q is the power set of Q, allowing the machine to transition to a set of possible next states (or none, if partial).[26] The operational semantics of an FSM are defined by its computation or run on an input string w = \sigma_1 \sigma_2 \dots \sigma_n \in \Sigma^*, starting from the initial state q_0 \in Q. The run proceeds iteratively: the state after the first symbol is q_1 = \delta(q_0, \sigma_1), then q_2 = \delta(q_1, \sigma_2), and so on, yielding a final state q_n = \delta(q_{n-1}, \sigma_n) after processing all symbols.[25] For a DFA, the run produces a unique sequence of states; for an NFA, it may produce a set of possible state sequences, with acceptance if at least one path reaches a state in the accepting set F \subseteq Q. The machine accepts w if q_n \in F.[27] To handle outputs, FSMs are classified into Moore and Mealy types, which differ in how outputs are generated during a run. In a Moore machine, outputs are associated solely with states, producing an output sequence where each output depends only on the current state (e.g., output at step k is a function of q_k).[28] In a Mealy machine, outputs are associated with state-input pairs, so the output at each step depends on both the current state and the input symbol (e.g., output for \sigma_k is a function of q_{k-1} and \sigma_k).[29] The language recognized by an FSM M, denoted L(M), consists of all strings w \in \Sigma^* that lead to an accepting state under the extended transition function \hat{\delta}: Q \times \Sigma^* \to 2^Q (or to Q for DFAs), defined recursively as \hat{\delta}(q, \epsilon) = \{q\} and \hat{\delta}(q, w\sigma) = \bigcup_{q' \in \hat{\delta}(q, w)} \delta(q', \sigma), with w \in L(M) if \hat{\delta}(q_0, w) \cap F \neq \emptyset.[25] Kleene's theorem establishes the equivalence between the languages recognized by FSMs and those described by regular expressions, showing that FSMs capture exactly the regular languages.[30]Representations
State Diagrams and Visual Notations
State diagrams provide a graphical representation of finite-state machines (FSMs), visually depicting the mathematical model where states are shown as nodes, typically circles or rounded rectangles, and transitions between states are illustrated as directed edges or arrows.[31] These edges are labeled with inputs that trigger the transition, and in output-producing FSMs, such as Mealy machines, the labels may also include corresponding outputs, for example, "coin/unlock" to denote an input event and its resulting action.[31] This notation allows designers to intuitively map the sequence of states and events, grounding the abstract components of states, transitions, and the transition function in a comprehensible visual form.[32] In object-oriented modeling, UML state machines extend traditional state diagrams with advanced features to handle more complex behaviors. States in UML are represented as rounded rectangles, which can contain nested substates for hierarchy, and transitions are arrows annotated with event triggers, guard conditions (Boolean expressions like [x > 0]), and actions (e.g., /setFlag). Entry and exit actions are specified within state compartments, executed automatically upon entering or leaving a state, while history states—denoted by a circle with an "H" for shallow history or "H*" for deep history—allow the machine to resume from the most recent active substate configuration after interruption. These extensions make UML state machines suitable for modeling reactive systems in software design.[33] SDL (Specification and Description Language) state machines, standardized by ITU-T for telecommunications systems, employ a graphical notation where states are depicted as rectangular boxes within process diagrams, and transitions are flow lines triggered by input signals or spontaneous events. Channels, represented as lines connecting blocks or processes, define communication paths with unidirectional or bidirectional signal routes, while signals—discrete events with optional parameters—are the primary inputs that consume from input queues to fire transitions. This structure supports concurrent, distributed systems by modeling agents (e.g., processes) as extended FSMs with explicit interfaces via gates and channels.[34][35] Other visual notations related to FSMs include Harel statecharts, which extend state diagrams with hierarchy and orthogonality to manage complexity in reactive systems; states can nest substates, and orthogonal regions allow parallel independent state machines within a superstate, with transitions broadcast across components. Petri nets, while distinct, model concurrency using places (circles), transitions (bars), and tokens, offering a graph-based alternative to FSMs for systems with multiple simultaneous states but differing in their emphasis on resource allocation rather than strict sequential transitions.[36][37] The primary advantages of state diagrams and their variants lie in their intuitiveness for design and debugging: they facilitate visual inspection of state sequences and transitions, enabling early detection of inconsistencies like conflicting inputs or unreachable states, which simplifies verification in complex FSMs compared to purely textual or tabular forms.[38]Tabular Representations
Tabular representations provide a structured, non-graphical method to specify finite-state machines (FSMs) by enumerating all possible state transitions in a matrix format, facilitating precise implementation and verification. Unlike visual diagrams, these tables offer an exhaustive listing of behaviors, making them suitable for automated processing and formal analysis.[39] The state-transition table is the primary tabular form, with rows representing the current states of the FSM and columns corresponding to possible inputs. Each cell in the table specifies the next state and, for output-producing FSMs, the associated output produced upon transition. This format encodes the FSM's transition function directly, allowing for straightforward translation into code or hardware logic, such as ROM-based implementations where the table serves as a lookup mechanism.[39] For deterministic FSMs, each input-state pair yields a unique next state, ensuring the table is complete without ambiguity.[40] A variant known as the state/event table emphasizes events—discrete occurrences that trigger transitions—over continuous inputs, which is particularly useful in reactive systems where behaviors respond to asynchronous signals like user actions or sensor triggers. In this representation, columns are labeled with events rather than inputs, and cells indicate the next state or no change (often denoted by a dash or self-reference), along with any actions. This approach highlights event-driven dynamics, making it easier to model systems with sporadic inputs, such as control software.[40][41] Tabular representations offer several advantages, including exhaustiveness that ensures all transitions are explicitly defined, reducing the risk of overlooked behaviors compared to graphical notations. They are compact for FSMs with few states and inputs, enabling easy automation in tools for simulation, verification, and code generation, and they support efficient hardware realization through direct mapping to combinational logic.[39][41] Additionally, tables clarify ignored events by including entries for non-effecting cases, promoting clarity in design.[40] Consider the classic turnstile example, a coin-operated gate with two states: Locked and Unlocked. Inputs are coin insertion and push attempts, with outputs controlling the lock mechanism. The state-transition table for this Mealy machine is as follows:| Current State | Input | Next State | Output |
|---|---|---|---|
| Locked | coin | Unlocked | unlock |
| Locked | push | Locked | none |
| Unlocked | coin | Unlocked | none |
| Unlocked | push | Locked | lock |