下推自动机

背景知识

PDA形式化描述

\[ \text{PDA} \quad M = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F) \tag{1} \] - \(Q\)：状态集合 - \(\Sigma\)：字母表 - \(\Gamma\)：栈符号表 - \(\delta\)：状态转移函数 - \(q_0\)：开始状态 - \(Z_0\)：栈底符号 - \(F\)：终态集合

其中状态转移函数为

\[ \delta : Q \times (\Sigma \cup \{\epsilon\}) \times \Gamma \rightarrow 2^{Q \times \Gamma^*} \tag{2} \]

即时描述

\[ (q, w, \gamma) \in Q \times \Sigma^* \times \Gamma^* \tag{3} \]

• 当前状态是 \(q\)
• 未处理的输入字符串是 \(w\)
• 栈中符号串是 \(\gamma\)

接受语言

有两种方式描述：

\[ L(M) = \{w \mid (q_0, w, Z_0) \vdash ^* (p, \epsilon, \beta) \text{ and } p \in F \} \tag{4} \]

\[ L(M) = \{w \mid (q_0, w, Z_0) \vdash ^* (p, \epsilon, \epsilon) \} \tag{5} \]

构造PDA

graph LR
    A["Get Grammar"] --> B["CFG"]
    B["CFG"] --> C["GNF"]
    C["GNF"] --"finial states"--> D["PDA"]
    C["GNF"] --"empty stack"--> D["PDA"]

PDA转换

终态换为空栈

已知终态接受的 PDA \(M_1\)，公式化构造空战接受的 PDA \(M_2\)，具体过程如下： \[ \text{PDA } M_1 = (Q, \Sigma, \Gamma, \delta_1, q_0, F) \tag{6} \]

\[ \text{PDA } M_2 = (Q \cup \{q_{02}, q_e \}, \Sigma, \Gamma \cup \{Z_{02} \}, \delta_2, q_{02}, Z_{02}, F) \tag{7} \]

We construct PDA \(M_2\) to simulates PDA \(M_1's\) function. And first step, we need to get in PDA \(M_1\).

\[ \delta_2(q_{02}, \epsilon, Z_{02}) = \{(q_{01}, Z_{01}Z_{02})\} \tag{8} \]

PDA \(M_2\) simulates each none \(\epsilon\) step of PDA \(M_1\).

\[ \forall (q, a, Z) \in Q \times \Sigma \times \Gamma, \delta_2(q, a, Z) = \delta_1(q, a, Z) \tag{9} \]

PDA \(M_2\) completely simulates PDA \(M_1\) transition function in none finial states.

\[ \forall (q, Z) \in (Q - F) \times \Gamma, \delta_2(q, \epsilon, Z) = \delta_1(q, \epsilon, Z) \tag{10} \]

In \(M_1's\) finial states, not only should \(M_2\) simulates \(M_1's\) \(\epsilon\) moves, but also simulates accepting moves.

\[ \forall (q, Z) \in F \times \Gamma, \delta_2(q, \epsilon, Z) = \delta_1(q, \epsilon, Z) \cup \\{(q_e, \epsilon)\\} \tag{11} \]

\(M_1's\) stacks having been empty and in finial states, \(M_2\) begins to cleat stack.

\[ \forall q \in F, \delta_2(q, \epsilon, Z_{02}) = \{(q_e, \epsilon) \} \tag{12} \]

\[ \forall q \in \Gamma \cup \{Z_{02} \}, \delta_2(q_e, \epsilon, Z) = \{(q_e, \epsilon) \} \]

Empty Stack to Finial State

已知空栈接受的 PDA \(M_1\)，要构造一个与之等价终态接受的 PDA \(M_2\)，核心思路在于只要 \(M_2\) 发现 \(M_1\) 在运行过程中将栈弹空，就可以进入终止状态。

公式化构造

设 PDA \(M_1\) 为

\[ \text{PDA } M_1 =\left(Q, \Sigma, \Gamma, \delta_1, q_{01}, Z_{01}, \Phi\right) \]

公式化构造 PDA \(M_2\)

\[ \text{PDA } M_2 = \left(Q \cup \{q_0, q_f\}, \Sigma, \Gamma \cup \{Z_{02} \}, \delta_2, q_{02}, Z_{02}, \{q_f\} \right) \]

其中状态转移函数 \(\delta_2\) 为

\[ \begin{align*} &\delta_2(q_{02}, \epsilon, Z_{02}) = \{(q_{01}, Z_{01} Z_{02})\} \\ &\forall(q, a, Z) \in Q \times (\Sigma \cup \{\epsilon\}) \times \Gamma, \quad \delta_2(q, a ,Z) = \delta_1(q, a, Z) \\ &\delta_2(q, \epsilon, Z_{02}) = \{(q_f, \epsilon)\} \end{align*} \]

CFG to Empty Stack

先考虑 \(L\) 为不含 \(\epsilon\) 的 CFL。\(G\) 是该语言对应的 GNF 文法，考虑用 PDA 模拟 GNF 的最左派生。

公式化构造

设 GNF \(G = (V, T, P, S)\)。

取 PDA \(M = (\{q\}, T, V, \delta, q, S, \Phi)\)

\(\forall A \in V, \quad a \in T, \quad \gamma \in V^{\ast}\) 我们有 \(\delta(q, a, A) = \{(q, \gamma) \mid A \to a\gamma \in P\}\)

补充 \(\{\epsilon\}\)

在 \(M\) 的基础上，构造 \(M_1\)，具体是

\[ M_1 = (\{q, q_0\}, T, V \cup \{Z\}, \delta_1, q_0, Z, \Phi) \]

对于状态转移函数 \(\delta_1\)，定义如下：

\[ \begin{align*} \delta_1(q_0, \epsilon, Z) &= \{(q_0, \epsilon), (q, S)\} \\ \delta_1(q, a, A) &= \delta(q, a, A) \end{align*} \]

Empty Stack to CFG

公式化构造

设 PDA \(M = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, \Phi)\)，取 CFG \(G = (V, \Sigma, P, S)\)，其中： \[ \begin{align*} V &= \{S\} \cup Q \times \Gamma \times Q，\text{特别地我们用$[q_i, A, q_j]$来表示变量} \\ P &= \{S \to [q_0, Z_0, q] \mid q \in Q\} \\ & \cup \{[q, A, q_{n + 1}] \to a[q_1, A_1, q_2][q_2, A_2, q_3] \dots [q_n, A_n, q_{n + 1} \mid (q_1, A_1A_2 \dots A_n) \in \delta(q, a, A) \text{且} a \in \Sigma \cup \{\epsilon\}, n \geq 1\} \\ & \cup \{[q, A, q_1] \to a \mid (q_1, \epsilon) \in \delta(q, a, A)\} \end{align*} \]

课后习题解答

8.(2) 构造空栈接受的 PDA

\[ \begin{align*} S &\to aBcB | bAAd \\ B &\to aBa | Da | \epsilon \\ A &\to bbA | \epsilon \\ D &\to d \\ \end{align*} \]

补充题

Question: PDA \(\to\) CFG 绘制此PDA状态转移图，按照定理7-4所述的文法构造方法进行转换。并对所得到的文法进行化简。

\[ \begin{align*} \delta(q_0, a, Z) &= \{(q_0, AZ)\} \tag{1} \\ \delta(q_0, a, A) &= \{(q_0, A)\} \tag{2} \\ \delta(q_0, b, A) &= \{(q_1, \epsilon)\} \tag{3} \\ \delta(q_1, \epsilon, Z) &= \{(q_2, \epsilon)\} \tag{4} \end{align*} \]

Answer:

根据 \((4)\) 式，可以判断这是一个空栈接受的 PDA。

设 PDA \(M = (Q, \Sigma, \Gamma, \delta, q_0, Z, \Phi)\)

公式化构造 CFG。

首先