Finite automaton

Finite automaton is the simplest model of computation capable of recognizing regular languages: a state machine that processes an input string one symbol at a time, transitioning between states according to a fixed transition function. Despite its simplicity, the finite automaton is not merely a pedagogical toy. It is the computational substrate onto which all regular expressions compile, and it demonstrates that recognizing a pattern does not require memory — only state. The equivalence between finite automata and regular expressions, proved by Stephen Kleene in the 1950s, is one of the foundational theorems of formal language theory. The finite automaton is the floor of the Chomsky hierarchy: any simpler, and you can only count; any more complex, and you need a stack. Pushdown automata occupy that next rung.