下推自动机能够对应 CFG。它是一个带有 “栈” 的 $\varepsilon-\text {NFA}$ 。

6.1 下推自动机的定义

6.1.1 通俗介绍

下推自动机与 $\varepsilon-\text {NFA}$ 类似，状态控制器可以在有限个状态之间转移（Finite Control）。但是它还有一个符号栈，可以推入（push）写入符号，或者弹出（pop）读取符号。栈的空间可以看作无限的。

image-20210616221744488

6.1.2 形式定义

PDA 的定义如下：

$$ M = (Q,T,\Gamma , \delta , q_0, z_0, F) $$
  1. $Q$：有穷状态集。有限控制器的状态集合
  2. $T$：有限输入字母表。
  3. $\Gamma$：有限下推栈字母表。
  4. $\delta$：转移函数。输入：当前状态，当前输入，当前栈顶。输出：新状态，栈顶替换的字符
  5. $q_0$：初态， $q_0 \in Q$
  6. $z_0$：下推栈的栈底最初符号，$z_0 \in \Gamma - T$
  7. $F$：终态集合

如下图，当处于状态 q 时，输入一个字符 $a$ ，则将栈顶 $Z$ 替换为 $\beta_i$ 或者 $\beta _j$

image-20210616223644789

记作：

$$ \begin{array}{l} \delta (q, a, Z)=\left\{\left (p_{1}, \beta_{1}\right),\left (p_{2}, \beta_{2}\right), \cdots,\left (p_{m}, \beta_{m}\right)\right\}, \quad \text {或} \\ \delta(q, \varepsilon, Z)=\left\{\left(p_{1}, \beta_{1}\right),\left(p_{2}, \beta_{2}\right), \cdots,\left(p_{m}, \beta_{m}\right)\right\} \end{array} $$

例子：设计 PDA，识别 $L_{01} = \{0^n1^n | n \geq 1\}$

思路：

当 PDA 读入 0 时，压入 0，当读入 1 时，弹出 0. 当字符串读取结束后，到达栈顶，则说明接受字符串。

设起始状态 $q_0$ ，

$q_0 \to q_0$ :

  • $0, 0/00$ (表示输入零，将栈顶的 0 替换为 00，相当于压入 0)
  • $0, Z_0/0Z_0$ (表示输入 0，将栈顶的 $Z_0$ 替换为 $0Z_0$，相当于压入 0)

当输入 1 后到达 $q_1$ :

$q_0 \to q_1$ :

  • $1, 0/\varepsilon$ (表示输入 1, 弹出 0)

$q_1 \to q_1$ :

  • $1, 0/\varepsilon $ (表示输入 1，弹出 0)

为了侦测串结束，只要检查栈顶是 $Z_0$ 即可：

$q_1 \to q_2$ :

  • $\varepsilon , Z_0 / Z_0$

注：00111 不会被接受

6.1.3 瞬时描述

定义元组 $(q,w,\gamma)$ 表示 PDA 处于状态 $q$，输入剩余串 $w$，栈为 $\gamma$，称为瞬时描述（ID，Instantaneous description）。

在 $\text {PDA} P$ 中， $(q, a w, Z \alpha)$ 到 $(p, w, \beta \alpha)$ 的变化，称为 ID 的转移 $\vdash_{P}$, 记为

$$ (q, a w, Z \alpha) \vdash_{P}(p, w, \beta \alpha) $$

$\vdash_{P}^{*}$ 表示 ID 的 0 次或多次转移。

6.2 PDA 接受的语言

6.2.1 PDA 的接受方式

PDA $P$ 以终态方式接受的语言，记为 $\mathrm {L}(P)$, 定义为

$$ \mathrm{L}(P)=\left\{w \mid\left(q_{0}, w, Z_{0}\right) \vdash^{*}(p, \varepsilon, \gamma), p \in F\right\} $$

$P$ 以空栈方式接受的语言，记为 $\mathrm {N}(P)$, 定义为

$$ \mathbf{N}(P)=\left\{w \mid\left(q_{0}, w, Z_{0}\right) \vdash^{*}(p, \varepsilon, \varepsilon)\right\} $$

终态方式接收，就是空转移到终态（$\varepsilon , Z_0 / Z_0$），即用明确的状态表示中止。

空栈方式接收，就是接收字符串时弹空（$Z_0/\varepsilon$），导致栈空，表明接受。可以在任何状态中止。

定理：若 PDA $P_F$ 以终态接受语言，则一定存在 PDA $P_N$ 以空栈方式接受同语言。

证明略。思路为用 $P_N$ 模拟 $P_F$

6.3 PDA 与 CFG 的等价性

6.3.1 文法转 PDA

PDA 的特点是弹出一个符号，压入一个串。因此可用此过程模拟 CFG 的最左推导。

例子：设计 $L = \{0^n 1^m | a \leq m \leq n\}$ 的 PDA

解：

要接受的字符串的特点是：0 多余 1

image-20210616235058191

PDA 如上图。功能：

  1. 输入 0，则压入
  2. 一旦输入了 1，则弹出 0. 1 可以和 0 成对弹出，也可以空转弹出，从而保证 0 的数量大于等于 1 的数量。扫描完露出栈顶。

image-20210616235514185

如上图，我们将 S 作为栈底符号。通过非确定方式在栈中产生足够的 01 串（0S1, 0S, 01）（类似穷举出所有可能）, 当栈顶是 0 或 1 时，不断匹配出栈。只要输入串和穷举中任何一个相同就引发接受。

其对应的文法：

$$ S \to 0S1 | 0S | 01 $$

就类似最左派生。

定理： $\forall \text {CFL} L, \exists \text {PDA} P \text {s.t.} L = \mathrm {N}(P)$

【例子】 为 $S\to aAA, A \to aS | bS | a$ 构造 PDA.

【分析与解答】

单状态 $q_0 \to q_0$ :

  • $\varepsilon , s/aAA$

  • $\varepsilon , A/aS$

  • $\varepsilon , A/bS$

  • $\varepsilon , A/a$

  • $a,a / \varepsilon $

  • $b,b / \varepsilon $

6.3.2 GNF 转 PDA

如果 $\mathrm {GNF}$ 格式的 $\mathrm {CFG} G=\left (V, T, P^{\prime}, S\right)$, 那么构造 $\mathrm {PDA}$

$$ P=(\{q\}, T, V, \delta, q, S, \varnothing) $$

构造特点：

只有一个状态 $q$ 并且是开始状态 输入符号表 T 刚好是终结符 栈符号表 V 刚好是非终结符 栈底符号刚好是开始符号 不需要终态，因为以空栈接受

为每个产生式，定义 $\delta$ 为:

$$ \delta(q, a, A)=\left\{(q, \beta) \mid A \rightarrow a \beta \in P^{\prime}\right\} $$

产生式定义为终结符 ($a$) 连接变元符号串 ($\beta$)

【例子】 为 GNF 文法 $S\to aAA, A \to aS | bS | a$ 构造 PDA.

【分析与解答】

单状态 $q_0 \to q_0$ :

  • $a,S/AA$
  • $a,A/S$
  • $b,A/S$
  • $a,A/\varepsilon $

6.3.3 PDA 转 CFG

定理：若 PDA P, $L = \mathrm {N}(P)$ 则 L 是 CFG.

【例子】 将 $\text {PDA} P = (\{p, q\}, (0,1), \{X,Z\}, \delta, q, Z)$ 转为 CFG. $\delta $ 定义如下：

(1) $\delta(q, 1, Z)=\{(q, X Z)\}$ (2) $\delta(q, 1, X)=\{(q, X X)\}$ (3) $\delta(q, 0, X)=\{(p, X)\}$ (4) $\delta(q, \varepsilon, Z)=\{(q, \varepsilon)\}$ (5) $\delta(p, 1, X)=\{(p, \varepsilon)\}$ (6) $\delta(p, 0, Z)=\{(q, Z)\}$

https://www.bilibili.com/video/BV1oE4116794?p=31&spm_id_from=pageDriver

$$ \begin{array}{l} \begin{array}{l|l} \hline \delta & \text {产生式} \\ \hline \text { (0) } & S \rightarrow[q Z q] \\ & S \rightarrow[q Z p] \\ \text { (1) } & {[q Z q] \rightarrow 1\left[q X_{0} q\right][q Z q]} \\ & {[q Z q] \rightarrow 1[q X p][p Z q]} \\ & {[q Z p] \rightarrow 1[q X q][q Z p]} \\ & {[q Z p] \rightarrow 1[q X p][p Z p]} \\ \text { (2) } & {[q X q] \rightarrow 1[q X q][q X q]} \\ & {[q X q] \rightarrow 1[q X p][p X q]} \\ & {[q X p] \rightarrow 1[q X q][q X p]} \\ & {[q X p] \rightarrow 1[q X p][p X p]} \\ \text { (3) } & {[q X q] \rightarrow 0[p X q]} \\ & {[q X p] \rightarrow 0[p X p]} \\ \text { (4) } & {[q Z q] \rightarrow \varepsilon} \\ \text { (5) } & {[p X p] \rightarrow 1} \\ \text { (6) } & {[p Z p] \rightarrow 0[q Z p]} \\ & {[p Z q] \rightarrow 0[q Z q]} \\ \hline \end{array}\\ \end{array} $$
$$ \begin{array}{l} \hline \text {消除无用符号} \\ \hline S \rightarrow[q Z q] \\ {[q Z q] \rightarrow 1[q X p][p Z q]} \\ {[q X p] \rightarrow 1[q X p][p X p]} \\ {[q X p] \rightarrow 0[p X p]} \\ {[q Z q] \rightarrow \varepsilon} \\ {[p X p] \rightarrow 1} \\ {[p Z q] \rightarrow 0[q Z q]} \\ \hline \end{array} $$

过程详解：

$S\to[qZ?]$

展开：

  • $S\to[qZp]$
  • $S\to[qZq]$

S 定义为所有的开始状态（ $q_0,z_0, p$ ）, $q_0 = q, z_0 = Z$ ， $p = p | q$

对于 $\delta (q, 1, Z) = \{(q, XZ)\}$

从状态 q, 为了弹出 Z，可能到达任意状态。消耗 1，Z 替换成 [X][Z].

消耗 1，到达 q：$[qZ?]\to 1 [qX?][?Z?]$

展开就是：

$$ \left\{\begin{array}{cc} & {[q Z q] \rightarrow 1\left[q X_{0} q\right][q Z q]} \\ & {[q Z q] \rightarrow 1[q X p][p Z q]} \\ & {[q Z p] \rightarrow 1[q X q][q Z p]} \\ & {[q Z p] \rightarrow 1[q X p][p Z p]} \\ \end{array}\right. $$

确定型下推自动机（DPDA）

如果对于每个输入，后续状态唯一，则为 DPDA。