โ Theory of Computation learning pathTheory of Computation ยท Module 7 of 10
Pushdown automata
Finite automata with a stack.
๐ Key ideas
- A PDA adds a stack to a finite automaton: it can push and pop symbols.
- PDAs recognise exactly the context-free languages.
- Example: for a^n b^n, push for each a and pop for each b.
- Nondeterministic PDAs are more powerful than deterministic ones (DPDAs).
- DPDAs correspond to the grammars used by practical parsers (LR).
๐ก Real-life example: A stack is like a pile of plates: you can only add or remove from the top, which is perfect for matching opening and closing brackets.
PDAPushdown automaton, an automaton with a stack
StackLast-in, first-out memory
DPDADeterministic pushdown automaton
Context-free languageLanguage recognised by a PDA