Machines That Recognize Patterns
A finite automaton is one of the simplest models of computation: a machine with a fixed number of states that reads input one symbol at a time and transitions between states according to predefined rules. Despite this simplicity, finite automata are powerful enough to underpin regular expressions, lexical analysis in compilers, network protocols, and hardware controllers. Every regex you write compiles down to one of these machines.
Deterministic vs. Nondeterministic
A deterministic finite automaton (DFA) has exactly one transition for each state-symbol pair — given a state and an input, the next state is uniquely determined. A nondeterministic finite automaton (NFA) allows multiple transitions or epsilon moves. Remarkably, the subset construction theorem proves that every NFA can be converted to an equivalent DFA, though the DFA may have exponentially more states.
The Limits of Finite Memory
Finite automata have no scratchpad memory beyond their current state. This means they cannot count unboundedly: the language of balanced parentheses, for instance, requires a pushdown automaton (which adds a stack). The pumping lemma provides a formal proof technique for showing a language is not regular — a key result in the Chomsky hierarchy of formal languages.
From Theory to Silicon
In hardware, finite state machines are implemented directly with flip-flops (one per state bit) and combinational logic (for transition functions). A 3-state FSM needs 2 flip-flops (since 2^2 ≥ 3). The state encoding, transition logic, and output logic are synthesized from HDL descriptions into actual gates — the same gates you explored in the Boolean gates simulator.