Stack-based computation for context-free language recognition
A pushdown automaton extends a finite automaton with an unbounded stack. This allows recognition of context-free languages (like balanced parentheses and aⁿbⁿ) that regular automata cannot handle. The stack enables "counting" and "matching" via push/pop operations. Context-free languages are exactly those recognized by PDAs (Chomsky hierarchy level 2). Note: aⁿbⁿcⁿ requires two counts simultaneously — it's context-sensitive, not context-free, and cannot be recognized by any PDA.