Finite-state machine

• 1. Introduction

  ›

  A finite-state machine sits inside a turnstile at a subway entrance, waiting. The arms are locked. A commuter drops a coin into the slot. In that instant, the machine shifts from one state to another, unlocks, and allows exactly one person through before locking again. That is the whole mechanism, and it is also a complete demonstration of one of the most elegant ideas in the mathematics of computation.

  The finite-state machine, also called a finite-state automaton or FSA, is an abstract model of computation. At any given moment it occupies exactly one state from a finite list of possible states. When it receives an input, it may transition to a different state. The machine is defined by four things: its list of states, its starting state, the inputs it can receive, and the rules that govern which transitions those inputs trigger.

  That spare description conceals an enormous range of applications. Traffic lights, elevators, combination locks, vending machines, programming language compilers, network protocols, and entire fields from linguistics to biology have drawn on this model. How a device so deliberately limited became so widely useful is what this documentary explores.

• 2. The Turnstile Model

  ›

  A turnstile controls entry to subways and amusement parks with three rotating arms at waist height. Initially those arms are locked, blocking passage. Dropping a coin into a slot unlocks them, allowing one person through. After that person passes, the arms lock again until the next coin arrives.

  As a state machine, the turnstile has exactly two states: Locked and Unlocked. Two inputs can affect it: inserting a coin, and pushing the arm. In the Locked state, pushing the arm does nothing at all, no matter how many times a frustrated commuter tries. Only a coin input shifts the state to Unlocked. Once Unlocked, inserting additional coins has no effect either. A push from a customer resets the state back to Locked.

  This behavior can be laid out in a state-transition table, listing the current state, the input received, the next state, and any resulting output. The same information can also be drawn as a state diagram, a directed graph where each state is a circle and each transition is an arrow labeled with its triggering input. A circular arrow on a node represents an input that leaves the machine in the same state. A filled dot with an arrow pointing to the Locked node marks the initial state. The turnstile shows how a precise, unambiguous system can be described in either form, and both representations carry identical meaning.

• 3. States, Transitions, and Actions

  ›

  A state is a description of a system waiting to execute a transition. A transition is the set of actions that fire when a condition is met or an event arrives. Those definitions feel abstract until you consider an audio system switching between radio and CD playback. In radio mode, a "next" command moves to the next station. In CD mode, the identical "next" command moves to the next track. The input is the same; the outcome differs because the state differs. That asymmetry is the point of the whole model.

  Beyond transitions, some finite-state machine representations also allow actions to be attached directly to states. An entry action fires whenever the machine enters that state. An exit action fires whenever the machine leaves it. These additions let designers capture behaviors that are not about changing state but about what happens at the moment of arrival or departure.

  The Specification and Description Language, a standard from the ITU, takes this further by embedding a full action language inside its graphical notation. SDL state machines can send events, receive events, start and cancel timers, launch concurrent state machines, and make decisions. They also include built-in data types, called Abstract Data Types, and a defined execution model, which makes the finite-state machine not just a diagram but a runnable specification.

• 4. Acceptors, Transducers, and Their Kin

  ›

  Finite-state machines divide into four main families: acceptors, classifiers, transducers, and sequencers. Each family handles the relationship between input and output differently.

  Acceptors, also called detectors or recognizers, answer a binary question: is this input accepted or rejected? Every state in an acceptor is either accepting or non-accepting. When all input has been consumed, the machine's current state determines the verdict. A classic example from the source is an acceptor that recognizes the string "nice," with only state 7 as the accepting state. A set of strings that some acceptor accepts exactly is called a regular language. Strings with an even number of zeroes form a regular language; strings whose length is a prime number do not.

  Classifiers generalize acceptors by producing output with more than two possible values. Transducers go further still, generating output based on the current state and the incoming input. Two specific transducer types matter enough to have their own names. A Moore machine produces output that depends only on state, using entry actions. An elevator door illustrates the pattern: the entry action for the "Opening" state starts a motor; the entry action for "Closing" reverses it; the "Opened" and "Closed" states stop the motor and signal completion. A Mealy machine, by contrast, lets output depend on both state and input, often reducing the total number of states needed. Sequencers, the fourth family, are a specialized subtype of acceptors and transducers that accept only a single-letter alphabet and produce a single output sequence.

• 5. Determinism and Its Limits

  ›

  In a deterministic finite automaton, every state has exactly one transition for each possible input. No ambiguity exists. In a non-deterministic automaton, a given input from a given state might lead to one transition, several transitions, or no transition at all. The surprising result is that for any non-deterministic finite-state machine, an equivalent deterministic one can always be constructed. The algorithm that achieves this is called the powerset construction. The resulting deterministic machine is usually more complex, but it performs identically.

  A finite-state machine with only one state has its own name: a combinatorial FSM. It permits actions only when transitioning into a state. This turns out to be useful when multiple state machines must cooperate and one part of the system is purely combinatorial; treating it as a degenerate FSM allows it to fit cleanly into the same design tools as its more complex neighbors.

  The FSM's most fundamental limitation is memory. Its memory is bounded by the number of states it has, which is always finite. A Turing machine, by contrast, can read and write to an unbounded tape, making it strictly more powerful. An FSM matches only a Turing machine whose head can only read, never write, and must always move from left to right. That restricted Turing machine and the FSM accept exactly the same set of formal languages. There are computational tasks a Turing machine can perform that an FSM simply cannot, and that boundary defines where the FSM's usefulness ends and where other models of computation must begin.

• 6. Where FSMs Live in Practice

  ›

  Electrical engineering, linguistics, computer science, philosophy, biology, mathematics, video game programming, and logic all use finite-state machines. Within computer science alone the list runs from hardware design through software engineering, network protocols, compilers, and computational linguistics.

  In hardware, a digital circuit implementation of an FSM needs three things: a register to hold the state variables, one block of combinational logic to determine the next state, and a second block to determine the output. A Medvedev machine is a specific hardware variant where the output connects directly to the state flip-flops, reducing the time delay between the flip-flops and the output. State encoding can also be chosen to minimize power consumption.

  In compilers, finite automata appear in the frontend of programming language processors. A lexical analyzer, built from one or more FSMs, reads a raw sequence of characters and produces a sequence of language tokens: reserved words, literals, and identifiers. A parser then takes those tokens and builds a syntax tree. Together, the lexical analyzer handles the regular parts of the grammar and the parser handles the context-free parts. That layered structure, with FSMs at the entry point, reflects how cleanly the model handles pattern recognition over streams of symbols. The Hopcroft minimization algorithm finds the smallest possible FSM that performs any given function, which matters when hardware resources or processing speed are constrained.

• 7. UML and Hierarchical Extensions

  ›

  The Unified Modeling Language introduced its own notation for state machines, and that notation deliberately extends the classical FSM. UML state machines add two concepts that the original model lacks: hierarchically nested states and orthogonal regions. Nesting lets one state contain other states inside it, so a machine can be both in a broad "operational" state and simultaneously in a specific sub-state within that category. Orthogonal regions allow a machine to be in multiple independent states at once, running parallel tracks of behavior.

  UML state machines also blend the behaviors of the two classic transducer types. They support actions that depend on both state and triggering event, as in a Mealy machine. They also support entry and exit actions tied to states rather than transitions, as in a Moore machine. A single UML state machine can therefore express behaviors that would require separate machines under the classical taxonomy.

  Alternative semantics go even further. Tools for embedded controller design combine hierarchical state machines with flow graphs and truth tables into a single formalism. These charts draw on work by David Harel, whose original state machines also supported hierarchically nested states and orthogonal regions. The common thread across all these extensions is the attempt to preserve the precision and analyzability of the finite-state machine model while giving designers enough expressive power to model complex real-world systems without resorting to unstructured code.