Finite Automaton

A finite automaton (or finite-state machine) is the Turing machine with its memory amputated. It has a finite set of states, a designated start state, some accepting states, and a transition rule that, on reading each input symbol, jumps from one state to another. There is no tape to write on — the machine's entire recollection of everything it has read is the single state it currently sits in.

That sounds crippling, and in a sense it is: a finite automaton can only recognize regular languages — patterns like "ends in .com", "has an even number of 1s", or "is a valid phone number". But that modest power is everywhere: every regex engine, lexer, vending machine, traffic light, and network protocol is a finite automaton in disguise.

Watch one decide

The machine below recognizes binary strings whose value is a multiple of three. It needs just three states — one for each possible remainder mod 3 — because the running remainder is the only thing it must remember. On each bit b it updates r \leftarrow (2r + b) \bmod 3. If it ends in state q_0 (remainder 0), the string is accepted.

Three states, six transitions, and the machine flawlessly tests divisibility on strings of any length — using a fixed amount of memory no matter how long the input grows. That bounded memory is the signature of a finite automaton.

What it can and cannot do

The reach of finite automata is captured by a beautiful equivalence: a language is recognizable by some finite automaton if and only if it can be described by a regular expression. Deterministic (DFA) and nondeterministic (NFA) variants look different but accept exactly the same languages — every NFA can be flattened into a DFA.

That single limitation — no unbounded counting — is exactly where the finite automaton ends and the universal computer begins. Everything else in this section is a study of what that extra memory buys you.

See also

• Turing Machine
• Church–Turing Thesis
• Complexity Class