Finite Automata

A finite automaton (or state machine) is the most stripped-down model of computation: a finite set of states, a start state, some accepting states, and transitions that move between states as it reads input one symbol at a time. No memory beyond the current state. When the input ends, it either sits in an accepting state (accept) or not (reject).

That’s it — and yet it models turnstiles, traffic lights, regex engines, TCP connection state, and vending machines. Anything that reacts to a stream of events with a bounded set of situations is a state machine.

A Deterministic Finite Automaton has exactly one transition per (state, symbol). Given an input, its path is fully determined. Here’s a DFA accepting binary strings with an even number of 1s:

Double circle = accepting. Start in even; each 1 flips even⇄odd, each 0 stays. End in even → accept. Two states, zero memory, and it counts parity of arbitrarily long input.

A Nondeterministic Finite Automaton may have several transitions for the same symbol (or none, or ε-moves that consume nothing). It accepts if any path leads to an accepting state. NFAs are often far easier to design — “guess and check” — yet no more powerful:

The catch: no memory. A DFA can’t count without bound. It cannot recognize aⁿbⁿ (n a’s then n b’s) because it would need to remember n, and n is unbounded while states are finite. This limit is provable — the pumping lemma: any sufficiently long accepted string has a middle section you can repeat (“pump”) and still be accepted, which aⁿbⁿ can’t survive.

That single limitation — finite memory — is exactly what the next models climb past. Add a stack → pushdown automata (matched brackets). Add an infinite tape → Turing machines (everything).