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:

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.
Author: Jeffrey D. Ullman

-Paid-

See also

-No Additional Notes-