下推自动机

背景知识

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

图8.(2)

补充题

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。

首先