A finite-state machine, also called a finite automaton, is the most basic abstract computer. It has a finite set of states, a current state, and a transition rule that says, for each state and each input symbol, which state to move to next. It has no memory beyond the single state it currently occupies. The Stanford Encyclopedia of Philosophy’s entry on Turing machines situates finite automata as one of these simple abstract computational devices, contrasting them with the unbounded tape of a Turing machine.
Because its memory is bounded by a fixed number of states, a finite-state machine cannot count without limit or match nested structures. What it can do is recognize exactly the regular languages: the patterns describable by regular expressions. This equivalence between machines and patterns is the reason regular expressions and finite automata are studied together.
A landmark result on these machines is Michael Rabin and Dana Scott’s 1959 paper “Finite Automata and Their Decision Problems,” which studies both deterministic and nondeterministic finite automata and proves, among other things, that adding nondeterminism does not let a finite automaton recognize any language a deterministic one cannot. Their work earned them the Turing Award and made finite automata a settled, rigorous foundation.
Finite-state machines are everywhere in working software, not just in theory. Lexical analyzers in compilers, network and communication protocols, the matching engines behind regular expressions, and user-interface logic that moves between well-defined modes are all naturally described as finite-state machines, which is why the model is one of the first things taught in a theory-of-computation course.