Automata theory

Automata theory studies abstract machines, the formal languages they recognize and transformations between machine descriptions. The machine's permitted memory and transition rules determine its power. A finite-state automaton stores only one of finitely many states; a pushdown automaton additionally has a stack, while a Turing machine has unbounded working storage.

For example, a two-state finite-state automaton recognizes binary strings containing an even number of ones: reading1 switches state, reading0 preserves it, and the initial state is accepting. In contrast, recognizing all strings $a^n{b}^n$ requires remembering an unbounded count, which a finite-state automaton cannot do. A pushdown automaton can push once per $a$ and pop once per $b$. These comparisons separate language recognition from implementation details and motivate closure properties, minimization and decidability questions.