= Automata theory
<Automata theory> studies abstract machines, the <formal language>[formal languages] they recognize and transformations between <abstract machine>[machine] descriptions. The <abstract machine>[machine]'s permitted memory and transition rules determine its power. A <finite-state automaton> stores only one of finitely many <state (computer science)>[states]; a <pushdown automaton> additionally has a <stack (data structure)>[stack], while a <Turing machine> has unbounded working storage.
For example, a two-state <finite-state automaton> recognizes <binary string>[binary strings] containing an even number of ones: reading1 switches <state (computer science)>[state], reading0 preserves it, and the initial <state (computer science)>[state] is accepting. In contrast, recognizing all strings $a^nb^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 <formal language>[language recognition] from implementation details and motivate closure properties, minimization and decidability questions.
Back to article page
