← all systems · see it in The System
Finite-state machine: an abstract machine in exactly one of finitely many states at a time, moved from state to state by its inputs; the lowest member of the automata hierarchy and a working design tool
In theoretical computer science, a finite-state machine (FSM) or finite-state automaton, finite automaton, or simply a state machine, is a mathematical model of computation.
Properties published scienceour proposal
Sourced fields, and our own readings.
| aliases | Finite-state machine (read-only, right-moving) |
| born at | August 1951 (Kleene's investigations, RAND RM-704); precursor 1943 (McCulloch and Pitts) |
| born precision | month (contested, C-3844) |
| boundary | Inside: the finite set of states, the current state held in a register, the transition function, the start and accepting states or the output function, and the run they make on an input read once from left to right. Outside: whoever or whatever supplies the input (a person, a network peer, a clock, a solution of molecules), what the outputs act on, the designer who chose the states and table, and the physical carrier when it is built. |
| nested level | A model of computation studied in automata theory, the bottom rung of the Chomsky hierarchy (below pushdown and linear bounded automata and Turing machines); built as sequential circuits, programs, protocol specifications and molecules; read into nerve nets, ribosomes and birdsong by the sciences that study them. |
| scale | technological |
Measures (29) published science
| characteristic clock: one transition per input symbol | 1 transition per symbol |
| Swiss railway clock: master-clock signal period | 60 s |
| Swiss railway clock: states | 720 states (one input symbol) |
| Swiss railway clock: second-hand sweep before the wait | about 58.5 s |
| TCP maximum segment lifetime (MSL) | 2 minutes (an engineering choice) |
| TCP TIME-WAIT duration | 2 MSL = 4 minutes |
| TCP connection states | 11 states (10 plus the fictional CLOSED) |
| NFA to DFA: worst-case states for an n-state NFA | 2^n (tight) states |
| alternating automaton to DFA: worst-case states | 2^(2^n) (tight) states |
| DFA minimisation time (Hopcroft) | O(n log n) time for an n-state DFA |
| states a finite-state grammar needs for an m-term dependency set | at least 2^m states |
| Cerny bound on the shortest synchronizing word (conjectured) | (n-1)^2 letters, for n states |
| best proven general bound on the shortest synchronizing word, from 2019 | alpha n^3 + o(n^3) with alpha <= 0.1654 letters |
| Rubik's cube as an FSM: states | 519,024,039,293,878,272,000 states (12 input symbols) |
| Rubik's cube as an FSM: transition table size | about 4.7 x 10^21 bytes (4 yottabytes) |
| Benenson DNA automaton: automata running in parallel | 10^12 automata in 120 microlitres |
| Benenson DNA automaton: combined transition rate | 10^9 transitions per second |
| Benenson DNA automaton: transition fidelity | greater than 99.8 % per transition |
| Benenson DNA automaton: power | less than 10^-10 W |
| recombinase state machines in E. coli: DNA states | up to 16 states (1 to 3 chemical inputs) |
| states in OpenSSL's learned TLS server machine, 1.0.1g to 1.0.2 | 16, 11, 10, 7 states |
| TLS implementations with new flaws found by state learning | 3 of 9 implementations |
| learning time for GnuTLS 3.3.8 server machine | 0:45 (12 states; 1,370 membership and 5,613 equivalence queries) h:mm |
| Bengalese finch song: effective context length | 8 preceding syllables (37 categories) |
| maximal degree of multiple center-embedding in written language | 3 (13 instances found) nested clauses |
| entropy production class of a regular language | zero if its minimal DFA is invertible; necessarily non-zero otherwise class |
| LSTM cell state complexity vs SRN | O(n^k) vs O(1) reachable values |
| Rubik's cube: states reachable from solved by face turns | 43,252,003,274,489,856,000 states (one-twelfth of the 519,024,039,293,878,272,000 arrangements; 12 orbits) |
| Benenson DNA automaton: transitions per automaton | about 10^-3 (one step roughly every 17 minutes) transitions per second per automaton |
Open contentions (4) open contention
Where sources or readings disagree. Both stay on the map.
- C-3823 Can a simple step-by-step machine describe birdsong, or does song have deeper structure?
booked: The map keeps the competing readings; none is ruled.
the other reading: traditional reading: nonhuman song follows short-range Markovian dynamics; Bengalese finch song needs about eight preceding syllables, beyond low-order Markov models but finite (Morita et al. 2021), and the length depends on how finely syllables are classified; Sainburg et al. say their result does not speak to any specific formal grammar - C-3844 Who first defined the finite-state machine?
booked: The map keeps the competing readings; none is ruled.
the other reading: McCulloch and Pitts 1943 as the first (the encyclopedia: 'among the first ... to introduce a concept similar to finite automata'); switching-circuit engineers (Huffman, Mealy 1955, Moore 1956) built the same structure under other names; Ashby calls the theories 'essentially homologous'; Rabin and Scott (1959) as the form used today (one-tape acceptor, nondeterminism) - C-3860 Can human language be described by a finite-state machine?
booked: The map keeps the competing readings; none is ruled.
the other reading: in use, nesting is bounded: at most three center-embeddings in writing, two in speech (Karlsson 2007, 2010), so a finite-state device could in principle cover what occurs; Chomsky himself grants a length-limited finite-state grammar would be possible but useless; no hard limit in large written corpora: heavy-tailed depth (Blasi et al. 2019; abstract and first pages read); at the level of sound and word structure, finite-state models are the field's standard: phonological rule systems as used need only finite-state power (Johnson 1972; Kaplan and Kay; read through Bird 2002 and Karttunen 1998), and weighted finite-state transducers carry large-vocabulary speech recognition (Mohri et al. 2002) - C-3883 Are recurrent neural networks no more powerful than finite-state machines?
booked: The map keeps the competing readings; none is ruled.
the other reading: trained SRNs and GRUs solved a counting task needing more than finite memory over the tested lengths; with small noise they failed (Merrill 2019's own experiment); with rational (unbounded-precision) weights recurrent nets simulate all Turing machines (Siegelmann and Sontag 1992); LSTMs count and GRUs do not, empirically (Weiss et al. 2018, read through Merrill 2019)
Cross-scale patterns seen here (20) our proposal
Shapes that recur when the same kind of problem is solved at different scales, and how each shows in Finite-state machine: an abstract machine in exactly one of finitely many states at a time, moved from state to state by its inputs; the lowest member of the automata hierarchy and a working design tool. Each links to every other system that shows it.
- causal ceiling (structural)
A limit set by structure, not by means: the automaton 'can know about the past ... only that it falls into one of r mutually exclusive classes' (Kleene); a^n b^n cannot be recognised because the exact count cannot be remembered; McCulloch and Pitts: knowledge built by nets 'is incomplete as to space - holding / entrainment (structural)
The whole sets its parts' clock: every Swiss railway clock advances only on the central master clock's minute signal, and its second hand waits at 12 until it comes; synchronous machines step on a shared clock, 'the same physical process at each iteration (or clock cycle)'. - nested ladder (structural)
The Chomsky hierarchy nests automata by the languages they recognise: finite automata at the bottom, then pushdown, linear bounded and Turing machines; inside recurrent networks, regular = SRN = GRU, strictly below LSTM, which is below the counter languages (Merrill). - same role, different builds (structural)
One job, holding a finite state and stepping it on each input, done by relays, gates and flip-flops, PLCs, software, nerve nets, a minute-hand mechanism, a turnstile's latch, DNA with a restriction enzyme and ligase, and recombinase-flipped DNA in E. coli; the ribosome and polymerases read as finite - same toolkit, independent builds (structural)
The finite-state transducer 'was developed under different names by different research communities': Ashby (1967, quoted in the encyclopedia) calls the finite-state machine, Shannon's noiseless transducer, his own state-determined system and the sequential circuit 'essentially homologous'. Mealy (19 - templating (structural)
One definition reused unchanged everywhere: alphabet, states, start state, transition function, final states; state tables, UML and SDL charts; Thompson's construction assembles any expression from one module per operator. - The carry (structural)
All three faces: overflow passed on (the Swiss railway clock's transition sends (h, 59) to (h+1, 0); a TTL counter is a state machine); the wait (the second hand waits at 12 for the master signal; TCP's TIME-WAIT waits 2 MSL, 4 minutes, before CLOSED); the lookahead (a DFA built ahead from all NFA s - The Payment to Entropy (structural)
A physical DFA that updates locally and periodically must produce entropy whenever its update merges two states on one symbol; languages whose minimal DFA is non-invertible are inherently costly (divisibility by 9 in base 3 costs, in base 2 it does not). Signal form too: Benenson's DNA automaton run - trade one property for another (structural)
States for speed and size: an n-state NFA can need 2^n DFA states (Rabin and Scott: nondeterminism builds powerful automata from few states); a Mealy machine needs fewer states than a Moore machine but its output follows the input at once; FSM reactivity is bought with modularity (Colledanchise and - Umwelt: each system carves its own slice of one shared medium (structural)
Each machine carves its slice of the world as a finite input alphabet: the turnstile knows only coin and push; a TLS learner must fix its alphabet and drop heartbeat messages to keep the model finite; Kleene's input cells are two-state, 'determined by the environment'. - who opens the door (structural)
A port opened ahead of time: TCP's LISTEN state is set up by a passive OPEN and waits for a connection request from any peer; every FSM's transition table is installed before any input arrives. - conservation law plus closure (partial)
The transition law leaves the starting point open: Kleene notes that without a specified initial state the state at time t is also a function of that state, and without a finite past it is not determined by the input at all; the initial-state rule closes the slot. - coordination-before-mapping (partial)
Controllers coordinate a sequence of actions (lift doors, traffic lights, a grab-and-throw robot) with no model of the world beyond the current state; the machine 'can know about the past' only its class. - namespace completeness (the map predicts its gaps) (partial)
The structure predicts its members: the Myhill-Nerode theorem says the minimal DFA has exactly as many states as there are classes of equivalent strings, so the classes predict the states before the machine is drawn; Cerny's family attains the conjectured bound for every n. - same shape, opposite sign (partial)
One transition map read in the two directions: it determines each next state but not the one before (McCulloch and Pitts: disjunction 'prevents complete determination of the one before'); where the map is invertible backward too, a physical DFA can run with zero entropy production, where it merges i - seed (partial)
Kleene's three operations on single symbols (union, concatenation, star) unpack every regular language; after 1968 the notation spread from one editor and one compiler into lex, sed, AWK, grep and the standard libraries of most programming languages. - the whole sets the local reference (partial)
The master clock fixes the minute every station clock reads; a synchronizing word (road colouring) brings every state to one, so the machine's own walk sets a shared reference regardless of where it started. - lightning (surface)
Each transition is a discrete flip after which the machine is not the same (coin: Locked to Unlocked), and a synchronizing word collapses every state to one; but nothing stored is released, so it is the shape's surface only. - partner-becomes-part (surface)
The product construction runs two DFAs as one machine whose states are pairs, so two machines become one; there is no gain/gain loop or inheritance, so surface only. - symmetry breaking (name the cut) (surface)
A synchronizing word takes a machine whose current state is unknown (all states alike) to one named state; the cut is the word; what follows is read from that state.
Valence: what it trades, and with whom (18) published science
Each exchange with a neighbour, read from both sides: who gains, who pays, and what carries it.
- Ribosome via sys:base-pairing · Finite-state machine: an abstract machine in exactly one of finitely many states at a time, moved from state to state by its inputs; the lowest member of the automata hierarchy and a working design tool gain
- DNA and genes via sys:aqueous-solution · Finite-state machine: an abstract machine in exactly one of finitely many states at a time, moved from state to state by its inputs; the lowest member of the automata hierarchy and a working design tool gain
- Neuron (nerve cell) via sys:electrochemical-gradient · Finite-state machine: an abstract machine in exactly one of finitely many states at a time, moved from state to state by its inputs; the lowest member of the automata hierarchy and a working design tool gain
- Thermal energy (heat, temperature and heat flow) via sys:thermal-energy · Finite-state machine: an abstract machine in exactly one of finitely many states at a time, moved from state to state by its inputs; the lowest member of the automata hierarchy and a working design tool loss
- Human (Homo sapiens) via sys:sensory-environment · Finite-state machine: an abstract machine in exactly one of finitely many states at a time, moved from state to state by its inputs; the lowest member of the automata hierarchy and a working design tool gain
- Grammar (the structure of a language, as linguistics describes it) via sys:acoustic-wave · Finite-state machine: an abstract machine in exactly one of finitely many states at a time, moved from state to state by its inputs; the lowest member of the automata hierarchy and a working design tool loss
- Computer memory via sys:electromagnetic-field · Finite-state machine: an abstract machine in exactly one of finitely many states at a time, moved from state to state by its inputs; the lowest member of the automata hierarchy and a working design tool gain
- Internet protocol suite (TCP/IP): the layered datagram protocols every host and router runs, the RFC record that specifies them, and the community that keeps them via sys:computer-network · Finite-state machine: an abstract machine in exactly one of finitely many states at a time, moved from state to state by its inputs; the lowest member of the automata hierarchy and a working design tool gain
- Algorithm (the practice of step-by-step procedures and the structure they compute) via sys:written-record · Finite-state machine: an abstract machine in exactly one of finitely many states at a time, moved from state to state by its inputs; the lowest member of the automata hierarchy and a working design tool gain
- Turing machine: the abstract machine that reads and writes one symbol at a time on an unbounded tape by a finite table of rules, the model of computation of logic and computer science via sys:written-record · Finite-state machine: an abstract machine in exactly one of finitely many states at a time, moved from state to state by its inputs; the lowest member of the automata hierarchy and a working design tool mixed
- Compiler via sys:written-record · Finite-state machine: an abstract machine in exactly one of finitely many states at a time, moved from state to state by its inputs; the lowest member of the automata hierarchy and a working design tool gain
- Logic gate via sys:electromagnetic-field · Finite-state machine: an abstract machine in exactly one of finitely many states at a time, moved from state to state by its inputs; the lowest member of the automata hierarchy and a working design tool gain
- Computer science (the field: the practice and the computation it studies) via sys:sensory-environment · Finite-state machine: an abstract machine in exactly one of finitely many states at a time, moved from state to state by its inputs; the lowest member of the automata hierarchy and a working design tool gain
- Parser via sys:written-record · Finite-state machine: an abstract machine in exactly one of finitely many states at a time, moved from state to state by its inputs; the lowest member of the automata hierarchy and a working design tool even
- Pushdown automaton via sys:written-record · Finite-state machine: an abstract machine in exactly one of finitely many states at a time, moved from state to state by its inputs; the lowest member of the automata hierarchy and a working design tool mixed
- Regular expression via sys:written-record · Finite-state machine: an abstract machine in exactly one of finitely many states at a time, moved from state to state by its inputs; the lowest member of the automata hierarchy and a working design tool gain
- Behavior tree via sys:written-record · Finite-state machine: an abstract machine in exactly one of finitely many states at a time, moved from state to state by its inputs; the lowest member of the automata hierarchy and a working design tool loss
- Recurrent neural network via sys:written-record · Finite-state machine: an abstract machine in exactly one of finitely many states at a time, moved from state to state by its inputs; the lowest member of the automata hierarchy and a working design tool gain
Partners and parts published science
Built from / builds (7)
- Head (reads and writes the scanned square)
- State register (one of finitely many m-configurations)
- Table of instructions (the transition function)
- FSMs against behavior trees for task switching in games and robots
- Automaton-based against backtracking regular-expression engines
- Input alphabet
- Output function (Moore or Mealy) or accepting states
Sits inside / holds (3)
- Human (Homo sapiens)
- Computer science (the field: the practice and the computation it studies)
- Automata theory
expressed by (16)
- Generation/Synthesis
- Recombination/Composition
- Scaffolding/Enablement (Meta-Tooling)
- Templating / Standardization
- Interoperability/Transduction (Bridging)
- Encapsulation & Modularity (Abstraction)
- Internal Coordination/Regulation
- Sensing/Scanning
- Trail-Marking / Externalized Memory (Stigmergy)
- Hypothesis Portfolio / Multiple Hypothesis Tracking
- Reactive Response
- Physical/Virtual Barrier
- Self-Monitoring
- Validation of Identity/Intention
- Quality Control & Error Correction
- Scheduled Build-and-Dismantle (On-Demand Structure)
floor filled by (21)
- DNA and genes
- Aqueous solution
- Human (Homo sapiens)
- Written record (durable external marks: texts, archives, canon)
- Computer memory
- Computer network
- Logic gate
- Computer science (the field: the practice and the computation it studies)
- Head (reads and writes the scanned square)
- State register (one of finitely many m-configurations)
- Table of instructions (the transition function)
- Compiler
- Parser
- Chomsky hierarchy
- Input alphabet
- Output function (Moore or Mealy) or accepting states
- Regular expression
- Automata theory
- Regular language
- Synchronizing word
- Restriction enzyme
represents (2)
Kinds (15)
- Turing machine: the abstract machine that reads and writes one symbol at a time on an unbounded tape by a finite table of rules, the model of computation of logic and computer science
- Deterministic finite automaton (DFA)
- Nondeterministic finite automaton (NFA)
- Mealy machine
- Moore machine
- Medvedev machine
- Finite-state transducer
- Acceptor (recognizer)
- Two-way finite automaton
- Alternating finite automaton
- Statechart (UML and Harel state machines)
- Benenson automaton (DNA finite automaton)
- Recombinase-based state machine (in living cells)
- Buchi automaton
- Weighted finite-state transducer
Notes published science
- A machine that checks, one digit at a time, whether a number is divisible by 9 must give off some heat if the number is written in base 3, but in the best case gives off none if it is written in base 2. That holds for machines that update one small piece at a time, the same way every clock tick: the simplest base-3 checker has to merge two paths into one state, and in that setting every merge costs entropy. (src:ouldridge-wolpert-2023)
- The word 'regular' in every programmer's 'regex' was a placeholder. Kleene, writing about nerve nets for the RAND Corporation in 1951, called his class of events 'regular' and added: 'We would welcome any suggestions as to a more descriptive term.' Nobody found one. (src:kleene-1951, src:wp:regular-expression)
- In 2015 two researchers let a program quiz nine TLS libraries message by message until it could draw each one's state machine. In three of the nine, odd extra states and paths in the drawings led them to new security flaws; some other drawings had extra states that were not flaws. OpenSSL's drawing shrank from 16 states to 7 over four versions. (src:de-ruiter-poll-2015)
Layers
The ways it takes in its world, where they meet, and how it acts back, each from L1 (where it meets the world) up.
a finite-state machine as automata theorists and engineers describe it: inputs read one symbol at a time, a finite set of states, a transition table, the run and its output, up to the language it recognises and the model people build and use (reader's view)
- L1: The input: a sequence of symbols from a finite alphabet (characters, bits, messages, coins and pushes, clock ticks, molecules), presented one at a time.
- L2: Reading one symbol: the head (or the sampled input lines) takes in the next symbol only; no going back, no record kept.
- L3: The current state: exactly one of finitely many states; all the machine knows of the past.
- L4: The transition function: state and input give the next state (a set in an NFA); in hardware the next-state logic.
- L5: The run and its outputs: the walk through the state graph, accept or reject at the end, Moore or Mealy outputs along the way. Runs may be infinite (reactive machines; Buchi automata).
- L6: What it computes: a regular language (or a transduction); the states as classes of equivalent pasts; one minimal machine per language.
- L7: The model and the practice: the bottom rung of the automata hierarchy with its proven limits, and the working tool of hardware, compiler, protocol, game and robot designers.
the boardroom (shared floors)
- L3: The complete state: the current internal state together with the input now arriving; exactly one of finitely many states at any time; the state at each moment fixed by the states of all cells one moment before.
- L4: The transition function (table): for each state and input, the next state (one in a DFA; a set, possibly empty, in an NFA; undefined means reject); in hardware the combinational next-state logic.
- L5: The run: the walk through the state graph that the input fixes; at the end accept or reject (acceptor), or outputs along the way (Moore: from the state; Mealy: from state and input); a synchronizing word drives every state to one. A run may also be infinite: reactive machines (TCP, turnstiles, traffic lights, game AI) never end, and are judged along the way (Buchi acceptance: an accepting state passed infinitely often).
- L6: What it computes: the regular language it accepts (Kleene: all and only regular events), the transduction it performs; the state as one of finitely many classes of pasts (Myhill-Nerode); the minimal machine; equivalence and emptiness decidable.
- L7: The model and its practice: the lowest member of the automata hierarchy (a read-only, right-moving Turing machine), with the limits that follow (no unbounded counting, the pumping lemma), held by people as the standard way to design and analyse hardware controllers, lexers and text search, protocols, game and robot behaviour, and to learn other systems' behaviour. Model checking verifies finite-state models of hardware and software against specifications.
way in: Events: messages, user calls and timeouts (protocol and software machines)
- L1: Segments and messages arriving over the network (SYN, ACK, RST, FIN; TLS handshake messages), calls from the local user, and timers running out.
- L2: Abstracted to an input alphabet the state machine knows (a learner must fix it; messages that make the model infinite are left out); a listening state waits for them.
way in: Input molecules (finite automata built from biomolecules)
- L1: Input encoded in double-stranded DNA (or chemical inducers for recombinase machines) mixed into a small volume of solution with the automaton's enzymes and software molecules.
- L2: Recognition by sticky ends: a rule (transition) molecule binds the state molecule where their single-stranded ends match, then the enzyme cuts.
way in: Input signals on wires (the machine built as a sequential circuit)
- L1: Input cells (lines) whose two states, quiet or firing (0 or 1), are set by the environment; the coin slot and the push arm of a turnstile.
- L2: Combinational logic takes the inputs together with the current state to work out the next state (and, in a Mealy machine, the output).
way in: Stimuli at receptors (the nerve net McCulloch, Pitts and Kleene began from)
- L1: Receptors fire on stimuli: in the founding worked example one skin receptor responds to heat and another to cold.
- L2: All-or-none firing of the input neurons, one synaptic delay per step: the input to the net at each moment.
way in: The clock tick (synchronous machines; the master clock)
- L1: A periodic signal: the same physical process at each clock cycle; for a Swiss railway clock, an electrical pulse each minute from a central master clock.
- L2: One input symbol, 'tick': each tick moves the machine one step; between ticks nothing changes (the second hand pauses at 12 until the signal).
way in: The current state (the inner channel: all the machine carries from step to step)
- L1: The state register: a register stores the current state (flip-flops, relays, a programmable logic controller, a variable in software, a DNA sequence).
- L2: Memory by state alone: no memory other than the current state; past inputs are forgotten except as which of finitely many classes they fall into.
way in: The next input symbol (the tape read one way)
- L1: The input: a finite string of symbols from an alphabet fixed in advance, on a one-dimensional tape (or typed on a keyboard, or a stack of punched cards).
- L2: The read head over one square: one symbol taken in, the head advances and never returns; no permanent record is kept; the machine stops when the tape runs out.
way out: Accept or reject: the yes or no answer
- L1: A light shows yes or no; in software a returned value (a match signal in text search).
- L5: At the end of the input: accepting state or not.
way out: Built and used: the model turned into circuits, programs, protocols and molecules
- L1: Hardware (logic gates and flip-flops, relays, PLCs), software, DNA: a physical machine with finitely many states.
- L6: A design: a state diagram or table, UML or SDL chart, a regular expression compiled to an automaton.
- L7: Designers choose the FSM as the standard structure for task switching, controllers and protocols (and argue over its limits).
way out: Control signals and actions on the world (Moore and Mealy outputs)
- L1: A motor started or stopped, an arm unlocked, a light changed, a signal to another state machine.
- L5: The output: from the state alone (Moore: entry actions) or from state and input (Mealy: input actions).
way out: Heat: the entropy a physical machine produces
- L1: Entropy produced into the surroundings: zero only for languages whose minimal DFA is invertible; power use can be lowered by state encoding.
- L4: A non-invertible local update: two states sent to one on the same symbol (a conflict state).
way out: Output molecules and gene expression (biomolecular machines)
- L1: A detectable output molecule in solution; in E. coli, genes switched on or off and the order of inputs written in DNA.
- L5: The final state encoded in an output molecule, or in the DNA's arrangement after recombination.
way out: Send a message (protocol machines)
- L1: A segment on the network to the peer, whose own state machine takes it as an event.
- L4: The transition's action: which message to send next (a SYN, an ACK, a FIN, an alert).
way out: Write the next state (the loop back to the inner channel)
- L1: The register now holds the new state, read on the next step.
- L3: The register takes the next state (at the clock edge in a synchronous circuit; the same physical process each cycle).
- L4: The transition selected for this state and input.