Finite-state machine

A finite-state machine (FSM) is a mathematical model of computation consisting of a finite set of states, transitions between those states triggered by inputs, and an initial state that determines the starting configuration. Despite its apparent simplicity, the finite-state machine is a universal descriptor for any system whose behavior can be completely determined by its current state and the next input — from the logic of a digital circuit to the lifecycle of a biological cell to the grammar of a regular language. The theory of finite-state machines, developed by McCulloch, Pitts, and later formalized by Rabin and Scott, establishes that even systems with severely bounded memory can exhibit complex behavior when cascaded, networked, or embedded in feedback loops. The FSM is the simplest computational model in the Chomsky hierarchy, yet it reappears in unexpected domains: as Markov chains in stochastic processes, as cellular automaton rules in spatial computation, and as reactive systems in control theory. The finite-state machine teaches that complexity does not require infinite memory — it requires the right topology of transitions.