下推自动机（PDA）是带有「内存」（堆栈）的 $\varepsilon$-NFA。堆栈在每次动作中都可以读取栈顶，并将一个元素压入栈顶，或从栈顶弹出一个元素。

形式定义

PDA $P$ 是七元组 $P=(Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$，与 $\varepsilon$-NFA 不同的地方有：

• $\Gamma$ 为「有穷栈字母表」，即栈能放入的字母集合。
• $\delta$ 状态转移函数的输入变量增加为 $Q\times (\Sigma\cup\{\varepsilon\})\times\Gamma$。
• $Z_0\in\Gamma-\Sigma$，栈底符号。

PDA 接受的语言

设 PDA $P=(Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$，取决于 PDA 停机的方式，它可以以两种方式接受语言。

以终态方式接受

$P$ 以终态方式接受的语言是 $\mathbf{L}(P)=\{w|(q_0, w, Z_0)\vdash^*(p, \varepsilon, \gamma), p\in F\}$。

以空栈方式接受

$P$ 以空栈方式接受的语言是 $\mathbf{N}(P)=\{w|(q_0, w, Z_0)\vdash^*(p, \varepsilon, \varepsilon)\}$。

从 CFG 到 PDA

将 $A\to X_1|X_2|\cdots|X_n$ 写成 $\delta(q, \varepsilon, A)=\{(q, X_1), (q, X_2)\cdots (q, X_n)\}$，然后加上 $\delta(q, 0, 0)=\{(q, \varepsilon)\}$，$\delta(q, 1, 1)=\{(q, \varepsilon)\}$。

从 PDA 到 CFG

设有空栈接受的 PDA $P=(Q, \Sigma, \Gamma, \delta, q_0, Z_0, \varnothing)$，构造 CFG。

1. 为 $Q$ 中的每个符号 $p$ 构造一个产生式 $S\to[q_0Z_0p]$。

2. 如果 $\delta(q, a, X)$ 包含 $(p, Y_1Y_2\cdots Y_n)$，构造一组产生式

   $$ [qXr_n]\to a[pY_1r_1][r_1Yr_2]\cdots[r_{n-1}Y_nr_n] $$

其中 $r_1,r_2,\cdots,r_n$ 是 $Q$ 中的任意 $n$ 个状态排列组合。