[形式语言] 05 Pushdown Automaton

下面使用构造证明。

这个证明的核心在于两点

1. \(M_1\) 进入终止状态后，要清空栈来接收（下面用 \(q_{\varepsilon}\) 来解决）
   • 如果 \(M_2\) 进入了 \(q_\varepsilon\)，则用空移动可以清栈，根据 NFA 的性质，此时输入也被读完才能接收
2. \(M_1\) 没到终止状态，\(M_2\) 栈空时不能误接收（下面用 \(q_{02}, Z_{02}\) 来解决）

设 PDA \(M_1 = (Q, \Sigma, \Gamma, \delta_1, q_{01}, Z_{01}, F)\)，下面构造 \(M_2 = (Q \cup \{q_{02}, q_{\varepsilon}\}, \Sigma, \Gamma \cup \{Z_{02}\}, \delta_2, q_{02}, Z_{02}, F)\)。并根据下面规则构建 \(\delta_{2}\)。

• \(M_2\) 启动后，立即进入 \(M_1\) 的初始 ID \(\delta_2(q_{02}, \varepsilon, Z_{02}) = \{(q_{01}, Z_{01}Z_{02})\}\)
• 在 \(M_1\) 的非空移动，\(M_2\) 直接模拟 \(\forall (q, a, Z) \in Q \times \Sigma \times \Gamma. \delta_2(q, a, Z) = \delta_1(q, a, Z)\)
• 在 \(M_1\) 非终态时的空移动也可以直接模拟 \(\forall(q, Z) \in (Q - F) \times \Gamma. \delta_2(q, \varepsilon, Z) = \delta_2(q, \varepsilon, Z)\)
• 当 \(M_1\) 进入终态时进行空移动，\(M_2\) 要额外模拟清栈 \(\forall(q, Z) \in F \times \Gamma. \delta_2(q, \varepsilon, Z) = \delta_1(q, \varepsilon, Z) \cup (q_\varepsilon, \varepsilon)\)
• \(M_1\) 栈空并且进入终态，\(M_2\) 也一定终止 \(\delta_2(q, \varepsilon, Z_{02}) = \{(q_\varepsilon, \varepsilon)\}\)
• \(M_2\) 清栈后可以接收 \(\forall Z \in \Gamma \cup \{Z_{02}\}. \delta_2(q_{\varepsilon}, \varepsilon, Z) = \{(q_{\varepsilon}, \varepsilon)\}\)

下面证明 \(L(M_1) = N(M_2)\)。

• 首先证明 \(L(M_1) \subseteq N(M_2)\)

  • 设 \(x \in L(M_1)\)，则 \((q_{01}, x, Z_{01}) \vdash_{M_1}^* (q, \varepsilon, \gamma)\)。由于 \(Z_{02}\) 与 \(M_1\) 无关，因此有

    \[(q_{01}, x, Z_{01}Z_{02}) \vdash_{M_1}^{*} (q, \varepsilon, \gamma Z_{02})\ (q \in F)\]

  • 根据定义，\(M_2\) 能模拟 \(M_1\) 的所有移动，并且在 \(M_{01}\) 的终态清栈，有

    \[(q_{01}, x, Z_{01}Z_{02}) \vdash_{M_2}^{*} (q, \varepsilon, \gamma Z_{02}) \vdash_{M_2}^{*} (q_{\varepsilon}, \varepsilon, \varepsilon) \ (q \in F)\]

  • 又因为 \((q_{02}, x, Z_{02}) \vdash_{M_2} (q_{01}, x, Z_{01}Z_{02})\)，则

    \[(q_{02}, x, Z_{02}) \vdash_{M_2} (q_{01}, x, Z_{01}Z_{02}) \vdash_{M_2}^{*} (q, \varepsilon, \gamma Z_{02}) \vdash_{M_2}^{*} (q_{\varepsilon}, \varepsilon, \varepsilon) \ (q \in F)\]

  • 即 \(x \in N(M_2)\)

• 然后证明 \(N(M_2) \subseteq L(M_1)\)

  • 设 \(x \in N(M_2)\)，将上面的过程反推即可：此时 \(M_2\) 最后必须进入清栈的状态且读完 \(x\)，因此 \(M_1\) 必然进入终态且读完 \(x\)，即 \(M_1\) 也接收 \(x\)

类似的，需要通过构造并证明等价性。

这个证明的核心在于提前放一个哨兵 \(Z_{02}\) 在 \(M_2\) 的栈中。在接收过程中发现栈顶是 \(Z_{02}\)，则说明栈空了，那么 \(M_2\) 应当立即进入终态。

设 PDA \(M_1 = (Q, \Sigma, \Gamma, \delta_1, q_{01}, Z_{01}, F)\)，下面构造 \(M_2 = (Q \cup \{q_{02}, q_{f}\}, \Sigma, \Gamma \cup \{Z_{02}\}, \delta_2, q_{02}, Z_{02}, \{q_f\})\)。并根据下面规则构建 \(\delta_{2}\)。

• \(M_2\) 启动后，开始模拟 \(M_1\) 的栈 \(\delta_2(q_{02}, \varepsilon, Z_{02}) = \{(q_{01}, Z_{01}Z_{02})\}\)
• 在 \(M_1\) 的非空移动，\(M_2\) 直接模拟 \(\forall (q, a, Z) \in Q \times \Sigma \times \Gamma. \delta_2(q, a, Z) = \delta_1(q, a, Z)\)
• 如果 \(M_1\) 的栈空时，立即进入终态 \(\delta_2(q, \varepsilon, Z_{02}) = \{(q_f, \varepsilon)\}\)

设 CFL 对应 GNF \(G(V, T, P, S)\)，使得 \(L(G) = L\)。

下面构造一个空栈接收的 PDA \(M = (\{q\}, T, V, \delta, q, S, \emptyset)\)，其中

\[\forall A \in V, a \in T. \delta(q, a, A) = \{(q, \gamma) | A \rightarrow a \gamma \in P\}\]

下面证明 \(L(M) = L(G) = L\)，设 \(w \in L\)，只要证明

\[(q, w, S) \vdash_M^n (q, \varepsilon, \alpha) \Leftrightarrow S \xRightarrow{n} wa \in P\]

• 首先证明充分性，对 \(|w|\) 进行归纳

  • 当 \(n = 1\) 时，\((q, a, S) \vdash_M^n (q, \varepsilon, \alpha)\)，此处 \(a \in T\)，则 \((q, \alpha) \in \delta(q, a, S)\)。根据定义，有 \(S \rightarrow a \alpha \in P\)，因此 \(S \Rightarrow a \alpha\)。

  • 设 \(n = k\) 时成立，当 \(n = k + 1\) 时，有 \(w = xa, |x| = k, a \in T\) 使得

    \[(q, w, S) = (q, xa, S) \vdash_M^n (q, a, A \beta_1) \vdash_M (q, \varepsilon, \beta_2 \beta_1) = (q, \varepsilon, \alpha)\]

    因此 \((q, \beta_2) \in \delta(q, a, A)\)，根据定义有 \(A \rightarrow a \beta_2 \in P\)。又根据归纳假设有 \((q, xa, S) \vdash_M^n (q, a, A \beta_1) \Rightarrow S \xRightarrow{n} x A \beta_1 \in P\)。因此有

    \[S \xRightarrow{n} x A \beta_1 \Rightarrow xa \beta_2 \beta_1 = xa \alpha = w\alpha \]

    假设成立。

• 然后证明必要性，同样用归纳的方法

  • 当 \(n = 1\) 时，\(S \Rightarrow w \alpha\)，其中 \(w \in T \wedge S \rightarrow w \alpha \in P\)，根据定义有 \((q, \alpha) \in \delta(q, w, S)\)，因此 \((q, w, S) \vdash_M (q, \varepsilon, \alpha)\)，成立

  • 设 \(n = k\) 时成立，当 \(n = k + 1\) 时，设 \(S \xRightarrow{k} xA\beta_1 \Rightarrow xa \alpha = xa\beta_2\beta_1\)，从中可知 \[A \rightarrow \alpha \beta_2 \in P\]

    因此根据定义有 \((q, \beta_2) \in \delta(q, a, A)\)，即

    \[(q, a, A) \vdash_M (q, \varepsilon, \beta_2)\]

    又根据归纳假设及 \(S \xRightarrow{k} xA\beta_1\) 有

    \[(q, xa, S) \vdash_M^k (q, a, A\beta_1)\]

    因此有

    \[(q, xa, S) \vdash_M^k (q, a, A\beta_1) \vdash_M (q, \varepsilon, \beta_2 \beta_1) = (q, \varepsilon, \alpha)\] 成立

综上所述，下面的结论成立

\[(q, w, S) \vdash_M^n (q, \varepsilon, \alpha) \Leftrightarrow S \xRightarrow{n} wa \in P\]

注意到 \(\alpha\) 的任意性，因此

\[(q, w, S) \vdash_M^n (q, \varepsilon, \varepsilon) \Leftrightarrow S \xRightarrow{n} w \in P\]

即 \(N(M) = L(G)\)

值得注意的是，这里最后还要考虑 \(\varepsilon \in L\) 的情况。首先构造 \(M = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, \emptyset)\) 使得 \(N(M) = L - \{\varepsilon\}\)，然后令

\[M’ = (Q \cup \{q_\varepsilon\}, \Sigma, \Gamma \cup \{Z_\varepsilon\}, \delta’, q_\varepsilon, Z_\varepsilon)\]

令

\[\delta(q, a, Z) = \begin{cases} \{(q_\varepsilon, \varepsilon), (q_0, Z_0)\}, & a = \varepsilon \\ \delta(q, a, Z), & a \ne \varepsilon \end{cases}\]

则 \(N(M’) = N(M) \cup \{\varepsilon\}\)

设 \(M = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, \emptyset)\)，取 CFG \(G = (V, \Sigma, P, S)\)，其中

\begin{aligned} V = \{& S\} \cup Q \cup \Gamma \cup Q \\ P = \{& S \rightarrow [q_0, Z_0, q] | q \in Q \} \\ \cup \{& [q, A, q_{n+1}] \rightarrow a[q_1, A_1, q_2][q_2, A_2, q_3] \dots [q_n, A_n, q_{n+1}] \\ & \quad | (q_1, A_1 A_2 \dots A_n) \in \delta(q, a, A) \wedge a \in \Sigma \cup \{\varepsilon\}, q_i \in Q]\} \\ \cup \{& [q, A, q_1] \rightarrow a | (q_1, \varepsilon) \in \delta(q, a, A)\} \end{aligned}

下面证明 \(L(G) = N(M)\)，即证明

\[[q, A, p] \xRightarrow{*} x \Leftrightarrow (q, x, A) \vdash^* (p, \varepsilon, \varepsilon)\]

• 首先证明充分性。设 \([q, A, p] \xRightarrow{n} x\)，对 \(n\) 进行归纳

  • 当 \(n = 1\) 时，必有 \(x \in \Sigma \cup \{\varepsilon\}\)，因此 \([q, A, p] \rightarrow x \in P\)，根据定义有 \((p, \varepsilon) \in \delta(q, a, A)\)，即 \((q, a, A) \vdash (p, \varepsilon, \varepsilon)\)，成立

  • 设 \(n \le k\) 时结论成立，即 \(([q, A, p] \xRightarrow{i} x) \Leftrightarrow ((q, x, A) \vdash^* (p, \varepsilon, \varepsilon))\ (1 \le i \le n)\)

  • 则当 \(n = k + 1\) 时，有

    \[[q, A, p] \Rightarrow a[q_1, A_1, q_2][q_2, A_2, q_3] \dots [q_n, A_n, q_{n+1}] \xRightarrow{k} a x_1 x_2 \dots x_n\]

    根据定义有 \((q_1, A_1 A_2 \dots A_n) \in \delta(q, a, A)\)。

    设 \([q_i, A, q_{i+1}] \xRightarrow{k_i} x_i\ (1 \le i \le n)\) 且 \(\Sigma k_i = k\)。由归纳假设有 \((q_i, x_i, A_i) \vdash^* (q_{i+1}, \varepsilon, \varepsilon)\)。

    因此

    \begin{aligned} (q, a x_1 x_2 \dots x_n, A) & \vdash (q_1, x_1 x_2 \dots x_n, A_1 A_2 \dots A_n) \\ & \vdash^* (q_2, x_2 \dots x_n, A_2 \dots A_n) \\ & \vdash^* \dots \\ & \vdash^* (q_n, x_n, A_n) \\ & \vdash^* (q_{n+1}, \varepsilon, \varepsilon) \end{aligned}

    成立

• 下面证明必要性。设 \((q, x, A) \vdash^n (p, \varepsilon, \varepsilon)\)，对 \(n\) 进行归纳

  • 当 \(n = 1\) 时，\((q, a, A) \vdash (p, \varepsilon, \varepsilon)\)，即 \(\delta(q, a, A) \ni (p, \varepsilon)\)，根据定义 \([q, A, p] \rightarrow a \in P\)，成立

  • 设当 \(n = k\) 时成立，即 \((q, x, A) \vdash^k (p, \varepsilon, \varepsilon) \Rightarrow [q, A, p] \xRightarrow{k} x\)

  • 则当 \(n = k + 1\) 时，设 \(x = a x_1 x_2 \dots x_n\)，则

    \[(q, x, A) = (q, a x_1 x_2 \dots x_n, A) \vdash (q, x_1 x_2 \dots x_n, A_1 A_2 \dots A_n)\]

    其中 \((q_i, x_i, A_i) \vdash^{k_i} (p, \varepsilon, \varepsilon)\)，则 \([q_i, A_i, q_{i+1}] \xRightarrow{k_i} x_i\)

    由于 \((q, x, A) \vdash (q, \varepsilon, A_1 A_2 \dots A_n)\)，因此有 \(\delta(q, x, A) \ni (q_1, A_1 A_2 \dots A_n)\)，根据定义有

    \[[q, A, q_{n+1}] \rightarrow a[q_1, A_1, q_2][q_2, A_2, q_3] \dots [q_n, A_n, q_{n+1}] \in P\]

    综上，有

    \begin{aligned} [q, A, q_{n+1}] & \xRightarrow a[q_1, A_1, q_2][q_2, A_2, q_3] \dots [q_n, A_n, q_{n+1}] \\ & \xRightarrow{*} a x_1 [q_2, A_2, q_3] \dots [q_n, A_n, q_{n+1}] \\ & \dots \\ & \xRightarrow{*} a x_1 x_2 \dots x_n = x \end{aligned}

    成立。

综上，原命题成立