โ† Theory of Computation learning path
Theory of Computation ยท Module 7 of 10

Pushdown automata

Finite automata with a stack.

๐Ÿ“– Key ideas

  1. A PDA adds a stack to a finite automaton: it can push and pop symbols.
  2. PDAs recognise exactly the context-free languages.
  3. Example: for a^n b^n, push for each a and pop for each b.
  4. Nondeterministic PDAs are more powerful than deterministic ones (DPDAs).
  5. 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