EVOPEDIA

← 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.

aliasesFinite-state machine (read-only, right-moving)
born atAugust 1951 (Kleene's investigations, RAND RM-704); precursor 1943 (McCulloch and Pitts)
born precisionmonth (contested, C-3844)
boundaryInside: 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 levelA 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.
scaletechnological

Measures (29) published science

characteristic clock: one transition per input symbol1 transition per symbol
Swiss railway clock: master-clock signal period60 s
Swiss railway clock: states720 states (one input symbol)
Swiss railway clock: second-hand sweep before the waitabout 58.5 s
TCP maximum segment lifetime (MSL)2 minutes (an engineering choice)
TCP TIME-WAIT duration2 MSL = 4 minutes
TCP connection states11 states (10 plus the fictional CLOSED)
NFA to DFA: worst-case states for an n-state NFA2^n (tight) states
alternating automaton to DFA: worst-case states2^(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 setat 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 2019alpha n^3 + o(n^3) with alpha <= 0.1654 letters
Rubik's cube as an FSM: states519,024,039,293,878,272,000 states (12 input symbols)
Rubik's cube as an FSM: transition table sizeabout 4.7 x 10^21 bytes (4 yottabytes)
Benenson DNA automaton: automata running in parallel10^12 automata in 120 microlitres
Benenson DNA automaton: combined transition rate10^9 transitions per second
Benenson DNA automaton: transition fidelitygreater than 99.8 % per transition
Benenson DNA automaton: powerless than 10^-10 W
recombinase state machines in E. coli: DNA statesup to 16 states (1 to 3 chemical inputs)
states in OpenSSL's learned TLS server machine, 1.0.1g to 1.0.216, 11, 10, 7 states
TLS implementations with new flaws found by state learning3 of 9 implementations
learning time for GnuTLS 3.3.8 server machine0:45 (12 states; 1,370 membership and 5,613 equivalence queries) h:mm
Bengalese finch song: effective context length8 preceding syllables (37 categories)
maximal degree of multiple center-embedding in written language3 (13 instances found) nested clauses
entropy production class of a regular languagezero if its minimal DFA is invertible; necessarily non-zero otherwise class
LSTM cell state complexity vs SRNO(n^k) vs O(1) reachable values
Rubik's cube: states reachable from solved by face turns43,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 automatonabout 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.

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.

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.

Partners and parts published science

Built from / builds (7)

Sits inside / holds (3)

expressed by (16)

floor filled by (21)

represents (2)

Kinds (15)

Notes published science

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)

  1. 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.
  2. L2: Reading one symbol: the head (or the sampled input lines) takes in the next symbol only; no going back, no record kept.
  3. L3: The current state: exactly one of finitely many states; all the machine knows of the past.
  4. L4: The transition function: state and input give the next state (a set in an NFA); in hardware the next-state logic.
  5. 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).
  6. L6: What it computes: a regular language (or a transduction); the states as classes of equivalent pasts; one minimal machine per language.
  7. 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)

  1. 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.
  2. 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.
  3. 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).
  4. 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.
  5. 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)

  1. L1: Segments and messages arriving over the network (SYN, ACK, RST, FIN; TLS handshake messages), calls from the local user, and timers running out.
  2. 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)

  1. 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.
  2. 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)

  1. 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.
  2. 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)

  1. L1: Receptors fire on stimuli: in the founding worked example one skin receptor responds to heat and another to cold.
  2. 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)

  1. 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.
  2. 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)

  1. L1: The state register: a register stores the current state (flip-flops, relays, a programmable logic controller, a variable in software, a DNA sequence).
  2. 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)

  1. 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).
  2. 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

  1. L1: A light shows yes or no; in software a returned value (a match signal in text search).
  2. 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

  1. L1: Hardware (logic gates and flip-flops, relays, PLCs), software, DNA: a physical machine with finitely many states.
  2. L6: A design: a state diagram or table, UML or SDL chart, a regular expression compiled to an automaton.
  3. 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)

  1. L1: A motor started or stopped, an arm unlocked, a light changed, a signal to another state machine.
  2. 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

  1. L1: Entropy produced into the surroundings: zero only for languages whose minimal DFA is invertible; power use can be lowered by state encoding.
  2. 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)

  1. L1: A detectable output molecule in solution; in E. coli, genes switched on or off and the order of inputs written in DNA.
  2. L5: The final state encoded in an output molecule, or in the DNA's arrangement after recombination.

way out: Send a message (protocol machines)

  1. L1: A segment on the network to the peer, whose own state machine takes it as an event.
  2. 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)

  1. L1: The register now holds the new state, read on the next step.
  2. L3: The register takes the next state (at the clock edge in a synchronous circuit; the same physical process each cycle).
  3. L4: The transition selected for this state and input.

Sources (43) published science

Turing machine (Wikipedia, rev 1380238390, 2026-10-14, via Wikimedia Enterprise snapshot 2026-11-01)
Finite-state machine (Wikipedia; Wikimedia Enterprise snapshot 2026-11-01)
Erickson, J. (2025) Models of Computation, Lecture 3: Finite-State Machines [Fa'25]. University of Illinois (CC BY-NC-SA 4.0; whole chapter) (behind its links)
Eddy, W. (ed.) (2022) RFC 9293: Transmission Control Protocol (TCP). IETF (section 3.3.2 state machine overview and section 3.4 on MSL) (behind its links)
de Ruiter, J. & Poll, E. (2015) Protocol state fuzzing of TLS implementations. USENIX Security 2015 (open access, Radboud/Birmingham repository; full text) (behind its links)
Colledanchise, M. & Ogren, P. (2017-2022) Behavior Trees in Robotics and AI: An Introduction. arXiv:1709.00084v6 (open book; sections 1.1-1.2 and 2.1-2.2 on FSMs) (behind its links)
Rabin, M. O. & Scott, D. (1959) Finite automata and their decision problems. IBM J. Res. Dev. 3(2), 114-125 (read in an open scanned copy, OCR; introduction and section 1 read in full, later chapters skimmed) (behind its links)
Kleene, S. C. (1951) Representation of events in nerve nets and finite automata. RAND Research Memorandum RM-704 (investigations of August 1951; published 1956 in Automata Studies, doi:10.1515/9781400882618-002). Read in a scanned open copy (OCR text; quotes repaired from OCR): introduction, sections 3, 7.1, 8 and 9 (behind its links)
Sainburg, T., Theilman, B., Thielk, M. & Gentner, T. Q. (2019) Parallels in the sequential organization of birdsong and human speech. Nat. Commun. 10, 3636, doi:10.1038/s41467-019-11605-y (PMC6690877; full text) (behind its links)
Automata theory (Wikipedia; WME snapshot; history, hierarchy and applications sections) (behind its links)
Holzer, M. & Kutrib, M. (2011; record year 2010) Descriptional and computational complexity of finite automata: a survey. Information and Computation, doi:10.1016/j.ic.2010.11.013 (OpenAlex stored full text) (behind its links)
Chomsky, N. (1956) Three models for the description of language. IRE Trans. Inf. Theory 2(3), 113-124, doi:10.1109/TIT.1956.1056813 (open scanned copy, OCR; abstract and section 2 on finite-state Markov processes) (behind its links)
Don, H. (2016) The Cerny conjecture and 1-contracting automata. Electron. J. Combin. 23(3), P3.12, doi:10.37236/5616 (introduction) (behind its links)
Shitov, Y. (2019) An improvement to a recent upper bound for synchronizing words of finite automata. J. Autom. Lang. Comb., doi:10.25596/jalc-2019-367 (abstract and introduction; 13 kB of text reached) (behind its links)
Benenson, Y., Paz-Elizur, T., Adar, R., Keinan, E., Livneh, Z. & Shapiro, E. (2001) Programmable and autonomous computing machine made of biomolecules. Nature 414, 430-434, doi:10.1038/35106533 (abstract only; superscripts lost in the record) (behind its links)
Roquet, N., Soleimany, A. P., Ferris, A. C., Aaronson, S. & Lu, T. K. (2016) Synthetic recombinase-based state machines in living cells. Science 353, aad8559, doi:10.1126/science.aad8559 (abstract only) (behind its links)
Morita, T., Koda, H., Okanoya, K. & Tachibana, R. O. (2021) Measuring context dependency in birdsong using artificial neural networks. PLoS Comput. Biol. 17, e1009707, doi:10.1371/journal.pcbi.1009707 (PMC8746767; full text) (behind its links)
Karlsson, F. (2010) Working memory constraints on multiple center-embedding. Proc. Annu. Meet. Cogn. Sci. Soc. 32 (open repository copy; full text) (behind its links)
Ouldridge, T. E. & Wolpert, D. H. (2023) Thermodynamics of deterministic finite automata operating locally and periodically. New J. Phys., doi:10.1088/1367-2630/ad1070 (gold OA; full text) (behind its links)
Merrill, W. (2019) Sequential neural networks as automata. Proc. Deep Learning and Formal Languages workshop (ACL), doi:10.18653/v1/w19-3901 (full text) (behind its links)
Rubik's Cube (Wikipedia; WME snapshot; section on permutations) (behind its links)
Thompson, K. (1968) Programming techniques: regular expression search algorithm. Commun. ACM 11(6), 419-422, doi:10.1145/363347.363387 (OpenAlex stored text, 15 kB: the whole four-page paper) (behind its links)
Regular expression (Wikipedia; WME snapshot; history and implementations sections) (behind its links)
Shapiro, E. (2012) A mechanical Turing machine: blueprint for a biomolecular computer. Interface Focus 2, 497-503, doi:10.1098/rsfs.2011.0118 (CC BY; PMC3363030) (behind its links)
Regular language (Wikipedia; WME snapshot; abstract and examples) (behind its links)
LR parser (Wikipedia, via Wikimedia Enterprise) (behind its links)
Soloveichik, D. & Winfree, E. (2005) The computational power of Benenson automata. Theor. Comput. Sci., doi:10.1016/j.tcs.2005.07.027 (introduction) (behind its links)
McCulloch, W. S. & Pitts, W. (1943) A logical calculus of the ideas immanent in nervous activity. Bull. Math. Biophys. 5, 115-133, doi:10.1007/BF02478259 (read in an OCR copy hosted for a University of Illinois course; whole text) (behind its links)
Nondeterministic finite automaton (Wikipedia; WME snapshot; abstract read) (behind its links)
Buchi automaton (Wikipedia; WME snapshot; abstract) (behind its links)
Mohri, M., Pereira, F. & Riley, M. (2002) Weighted finite-state transducers in speech recognition. Computer Speech & Language 16, 69-88, doi:10.1006/csla.2001.0184 (green OA; introduction and definitions; 'fi' ligatures lost in the text) (behind its links)
Pumping lemma for regular languages (Wikipedia; WME snapshot; abstract read) (behind its links)
Mealy machine (Wikipedia; WME snapshot) (behind its links)
Moore machine (Wikipedia; WME snapshot; abstract read) (behind its links)
Deterministic finite automaton (Wikipedia; WME snapshot; abstract and opening read) (behind its links)
Trahtman, A. N. (2007) The road coloring problem. arXiv:0709.0099 (Israel J. Math.; abstract and introduction) (behind its links)
Blasi, D. E., Cotterell, R., Wolf-Sonkin, L., Stoll, S., Bickel, B. & Baroni, M. (2019) On the distribution of deep clausal embeddings: a large cross-linguistic study. Proc. ACL 2019, doi:10.18653/v1/p19-1384 (abstract and first pages: 15 kB of text reached) (behind its links)
Szykula, M. (2018) Improving the upper bound on the length of the shortest reset words. STACS 2018, doi:10.4230/LIPIcs.STACS.2018.56; arXiv:1702.05455 (abstract and introduction read; full text held) (behind its links)
Karttunen, L. (1998) The proper treatment of optimality in computational phonology. FSMNLP'98, doi:10.3115/1611533.1611534 (introduction and section on rewrite rules and two-level constraints) (behind its links)
Bird, S. (2002) Computational phonology. arXiv:cs/0204023 (encyclopedia chapter; history section read; short text reached) (behind its links)
Model checking (Wikipedia; WME snapshot; abstract and history) (behind its links)
Vaandrager, F. (2017) Model learning. Commun. ACM 60(2), 86-95, doi:10.1145/2967606 (green OA; introduction and the sections on L* and black box checking) (behind its links)
Siegelmann, H. T. & Sontag, E. D. (1992) On the computational power of neural nets. COLT '92, doi:10.1145/130385.130432 (abstract and introduction) (behind its links)