Pushdown automata
Automata with finite states plus a stack enabling recognition of context-free languages. Pushdown automata are more powerful than FSMs, recognizing languages like balanced parentheses. Stack provides memory beyond state.
Formula
δ(state, input, stack_top) = (new_state, stack_operation)
Real World
Every web browser uses a pushdown automaton-like mechanism to check that HTML tags are properly nested — when it encounters <div>, it pushes onto a stack, and when it sees </div>, it pops, ensuring every opening tag has a matching close.
Exam Focus
Always state that PDAs are more powerful than FSMs because the stack provides additional memory beyond finite states.
How well did you know this?