7.2.1. 下推自动机与上下文无关语言¶

现在我们想要说明，NPDA 和 CFG 都能表示 CFL。也就是说，对于任何 CFG ，我们都可以构造出一个 NPDA ，反之亦然。

定理: 对于任何不包含 \(\lambda\) 、 \(\exists\) 的 CFL \(L\) ，以及一个 NPDA \(M\) ，使得 \(L = L(M)\) 。

证明（Proof）（概要）

给定（不含 \(\lambda\) 的）CFL \(L\)。

\(\Rightarrow \exists\) CFG \(G\) ，使得 \(L = L(G)\)。

\(\Rightarrow \exists G'\) （格雷巴赫范式，Greibach normal form，GNF），使得 \(L(G) = L(G')\)。

\(G' = (V,T,S,P)\) 。\(P\) 中的所有产生式都具有如下形式：

\(A \rightarrow ax\)

\(A \in V, a \in T, x \in V^*\)

构造 NPDA \(M = (Q, \Sigma, \Gamma, \delta, q_0, z, F)\)

\(Q = \{q_0, q_1, q_f\}, \Sigma = T, \Gamma = V \cup \{z\}, F = \{q_f\}\)

1. \(M\) 先把 \(S\) 放到栈上

2. 对每个产生式

\(A \rightarrow a X_1 X_2 \ldots X_n\)

将 \((q_1, X_1 X_2 \ldots X_n)\) 放入 \(\delta(q_1, a, A)\)

（从栈中弹出 \(A\) ，从带上读取 "a" ， 并把 \(X_1 X_2 \ldots X_n\) 压入栈）

3. 如果 \(S \stackrel{*}{\Rightarrow} w \in \Sigma^*\) 则接受 （栈上的所有变量都被终结符或 \(\lambda\) 替换）

证明 \(w \in L(G')\) 当且仅当 \(w \in L(M)\) 。证毕（QED）。

现在我们想要说明，给定一个 NPDA ，我们可以构造出一个 CFG。不过首先，我们将给出一个结论，以便简化接下来的证明。

定理: 给定一个 NPDA \(M\) , \(\exists\) 以及一个 NPDA \(M'\) ，其中所有过渡形式为 \(\delta(q_i, a, A) = \{c_1, c_2, \ldots c_n\}\)

每一次移动要么使栈的内容增加一个符号，要么减少一个符号。

证明（Proof）： （概要）

定理（Theorem）： 如果存在某个 NPDA \(M\) 使得 \(L = L(M)\) ，则 \(L\) 是 CFL。

Settings

Saving...
Server Error
Resubmit

证明（Proof）：

给定 NPDA \(M\) ，首先构造一个更容易处理的等价 NPDA \(M'\)。 构造 \(M'\) 使得

1. 栈为空时 \(M'\) 接受

2. 每一次移动都使栈的内容增加或减少一个符号。 （每条转移只能压入 2 个变量或不压入任何变量。）

\(M' = (Q, \Sigma, \Gamma, \delta, q_0, z, F)\)

构造 \(G = (V,\Sigma, S, P)\) ，其中

\(V = \{(q_icq_j)\ |\ q_i, q_j \in Q, c \in \Gamma \}\)

（其中一些变量将是多余的。）

\((q_icq_j)\) 表示"从状态 \(q_i\) 出发，且栈的内容为 \(cw, w \in \Gamma^*\) ，沿某条路径到达状态 \(q_j\) ，此时栈的内容为 \(w\)"。

目标：\((q_0zq_f)\) 将成为文法的起始符号。

含义：我们从状态 \(q_0\) 、栈上有 \(z\) 开始， 处理输入带。最终我们会到达最终状态 \(q_f\) ，此时栈为空。（沿途我们可能会把符号压入栈中，但这些符号最终都会从栈中弹出。）

（注：机器按空栈接受，但它是这样设计的： 只有 1 个最终状态能让机器按最终状态接受。）

为构造 P 中的产生式，可以这样做：

1) 将

替换为

\[(q_iAq_j) \rightarrow a\]

其中栈的变化为：

\[\begin{split}\begin{array}{lcclc} & q_i & \ \ (\mbox{some path}\ \rightarrow) \ \ & &q_j \\ \\ \mbox{stack:} & A && \mbox{stack:} & \\ & X_1 & && X_1 \\ & X_2 &&& X_2 \\ & \underline{X_n} &&& \underline{X_n} \\ \end{array}\end{split}\]

2) 将

替换为

\[(q_iAq_k) \rightarrow a(q_jBq_l)(q_lCq_k)\ \mbox{for all}\ q_l, q_k \in Q\]

\[\begin{split}\begin{array}{ccccccc} q_i & \ \ (\mbox{path}\ \rightarrow) \ \ & q_j &\ \ (\mbox{path}\ \rightarrow) \ \ & q_l &\ \ (\mbox{path}\ \rightarrow) \ \ & q_k \\ \\ &&B&& \\ A && C &&C \\ X_1 & & X_1 & & X_1 & & X_1 \\ X_2 && X_2 && X_2 && X_2 \\ \underline{X_n} &&\underline{X_n} &&\underline{X_n} &&\underline{X_n}\\ \end{array}\end{split}\]

这会产生一些无用的变量，但没关系。

必须证明所构造的文法 \(G\) 满足 \(L(G) = L(M')\)。也就是说，\(w \in L(G) \mbox{iff}\ w \in L(M)\)。（见教材）证毕（QED）。