3. 下推自动机与上下文无关语言¶
3.1. 下推自动机与上下文无关语言¶
在本模块中，我们讨论 NPDA 与 CFL 之间的关系。 剧透警告：NPDA 能够识别 CFL。
3.2. 将 CFG 转换为 NPDA¶
3.3. 将 NPDA 转换为 CFG¶
现在我们要说明，给定一个 NPDA，我们可以构造出一个 CFG。 不过首先，我们将给出一个结论，以便简化接下来的证明。
定理（Theorem）： 给定一个 NPDA \(M\)，存在一个 NPDA \(M'\)，使得所有转移都具有形式 \(\delta(q_i, a, A) = \{c_1, c_2, \ldots c_n\}\)，其中
\[\begin{split}\begin{eqnarray*}
c_i &=& (q_j, \lambda)\\
\mbox{or}\ c_i &=& (q_j, BC)\\
\end{eqnarray*}\end{split}\]
这一限制的后果是，每一次移动要么使栈的内容增加一个符号，要么减少一个符号。
证明（Proof）： （略）
我们可以通过如下方式替换 PDA 中变量过多或过少的任何转移，从而得到期望的受限形式。
定理（Theorem）： 如果存在某个 NPDA \(M\) 使得 \(L = L(M)\)， 则 \(L\) 是 CFL。
我们想要证明每个 NPDA 都表示一个 CFL，因此我们将取一个 NPDA \(M\) 并将其转换为 CFG。 如果我们先把 NPDA 的所有转移置于更简单的形式，构造起来会更容易。
证明概要：
给定 NPDA \(M\) ，首先，构造一个等价的 NPDA
\(M'\) ，使其满足简化假设。
反转从文法生成 PDA 的过程
以在文法中模拟该 PDA
栈的内容应反映在句型的变量
部分中
已处理的输入是句型的终结符前缀
形式
