# 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-