pushdown automata
(60 minutes to learn)
Summary
Pushdown automata are a simple model of computation where the memory consists of an (unbounded) stack of symbols. Nondeterministic pushdown automata are equivalent in expressive power to context-free grammars. Deterministic pushdown automata can recognize only a smaller set of languages, but most modern programming languages are recognizable by a deterministic pushdown automaton.
Context
This concept has the prerequisites:
- context-free grammars (Pushdown automata are equivalent in expressive power to context-free grammars.)
- finite automata (The definition of pushdown automata parallels that of finite automata.)
Goals
- Define the pushdown automaton, both the deterministic and nondeterministic versions.
- Be able to program pushdown automata to recognize simple languages.
- Give an example of a language recognizable by a nondeterministic, but not by a deterministic, pushdown automaton.
- Be aware that nondeterministic pushdown automata are equivalently expressive to context-free grammars.
- Prove that nondeterministic pushdown automata are equivalently expressive to context-free grammars.
Core resources (read/watch one of the following)
-Free-
→ Coursera: Automata
An introductory course on automata and the theory of computation.
-Paid-
→ Introduction to the Theory of Computation
An undergraduate textbook on automata and the theory of computation.
Location:
Section 2.2, "Pushdown automata," pages 109-122
→ Automata Theory, Languages, and Computation
An undergraduate textbook on automata and the theory of computation.
Location:
Chapter 6, "Pushdown automata," pages 225-258
See also
-No Additional Notes-