# 下推自动机

## 形式定义

PDA 形式定义为 6-元组：

${\displaystyle M=(Q,\ \Sigma ,\ \Gamma ,\ \delta ,\ q_{0},\ F)}$ 这里的

• ${\displaystyle \,Q}$状态的有限集合
• ${\displaystyle \,\Sigma }$ 是输入字母表的有限集合
• ${\displaystyle \,\Gamma }$字母表的有限集合
• ${\displaystyle \,\delta }$: ${\displaystyle Q\times \Sigma _{\epsilon }\times \Gamma _{\epsilon }\longrightarrow {\mathcal {P}}(Q\times \Gamma _{\epsilon })}$转移函数
• ${\displaystyle q_{0}}$ 是“开始状态”
• ${\displaystyle F\subset Q}$ 是“接受状态”的集合
• ${\displaystyle \Gamma _{\epsilon }=\Gamma \cup \{\epsilon \}}$
• ${\displaystyle \Sigma _{\epsilon }=\Sigma \cup \{\epsilon \}}$

(i) ${\displaystyle \ \ (q_{i+1},b_{i+1})\in \delta (q_{i},w_{i+1},a_{i+1})}$ 对于 i = 0, 1, 2,......, n-1,

(ii) ${\displaystyle \exists \,s_{0},\,s_{1},\,s_{2},\,s_{3},\,\cdots ,\,s_{n}\,\in \Gamma ^{*}}$ 使得

${\displaystyle s_{i}=a_{i+1}t_{i},\,s_{i+1}=b_{i+1}t_{i},\,t_{i}\in \Gamma ^{*}}$

${\displaystyle a_{i+1}\,}$${\displaystyle b_{i+1}\,}$ 二者都可以 ${\displaystyle \epsilon \,}$

(i) 对于每个 i = 0, 1, 2,...m，${\displaystyle r_{i}\,}$ 都在计算路径上。就是说

${\displaystyle \exists f(i)}$ 这里的 ${\displaystyle i\leq f(i)\leq n}$ 使得 ${\displaystyle r_{i}=q_{f(i)}\,}$

(ii) ${\displaystyle (q_{f(i)+1},b_{f(i)+1})\in \delta (r_{i},w_{i+1},a_{f(i)+1})}$ 对于每个 i = 0, 1, 2,...m-1。

(iii) ${\displaystyle (q_{j+1},b_{j+1})\in \delta (q_{j},\epsilon ,a_{j+1})}$，如果 ${\displaystyle q_{j}\notin \{r_{0},r_{1},\cdots r_{m}\}}$

(iv) ${\displaystyle r_{m}=q_{n}\,}$${\displaystyle r_{m}\in F}$

(iii) ${\displaystyle \delta }$(r1, 0, ${\displaystyle \epsilon }$) = ${\displaystyle \delta }$(q2, 0, ${\displaystyle \epsilon }$) ${\displaystyle \rightarrow }$ (q2, 0)
s2 = 0$, a = ${\displaystyle \epsilon }$, t = 0$, b = 0, s3 = 00$设置 r2 = q2 (iv) ${\displaystyle \delta }$(r2, 1, 0) = ${\displaystyle \delta }$(q2, 1, 0) ${\displaystyle \rightarrow }$ (q3, ${\displaystyle \epsilon }$) s3 = 00$, a = 0, t = 0$, b = ${\displaystyle \epsilon }$, s4 = 0$

(v) ${\displaystyle \delta }$(r3, 1, 0) = ${\displaystyle \delta }$(q3, 1, 0) ${\displaystyle \rightarrow }$ (q3, ${\displaystyle \epsilon }$)
s4 = 0$, a = 0, t =$, b = ${\displaystyle \epsilon }$, s5 = $(vi) ${\displaystyle \delta }$(q3, ${\displaystyle \epsilon }$,$) ${\displaystyle \rightarrow }$ (q4, ${\displaystyle \epsilon }$)
s5 = $, a =$, t = ${\displaystyle \epsilon }$, b = ${\displaystyle \epsilon }$, s6 = ${\displaystyle \epsilon }$

(b) 输入字符串 = 001

(v) ${\displaystyle \delta }$(r3, ${\displaystyle \epsilon }$, a) = ${\displaystyle \delta }$(q3, ${\displaystyle \epsilon }$, a)

(c) 输入字符串 = ${\displaystyle \epsilon }$

${\displaystyle \delta }$(r0, ${\displaystyle \epsilon }$, ${\displaystyle \epsilon }$) ${\displaystyle \rightarrow }$ (q1, ${\displaystyle \epsilon }$)

## 广义下推自动机(GPDA)

GPDA 是在一个步骤内写入整个字符串到栈上或从栈上去除整个字符串的 PDA。

GPDA 形式定义为 6-元组 ${\displaystyle M=(Q,\ \Sigma ,\ \Gamma ,\ \delta ,\ q_{0},\ F)}$

${\displaystyle \,\delta }$: ${\displaystyle Q\times \Sigma _{\epsilon }\times \Gamma ^{*}\longrightarrow {\mathcal {P}}(Q\times \Gamma ^{*})}$ 是转移函数。

GPDA 的计算规则同于 PDA，除了 ai+1 和 bi+1 现在是字符串而不是符号之外。

GPDA 和 PDA 是等价的，如果一个语言可被一个 PDA 识别，它也可被一个 GPDA 识别，反之亦然。

${\displaystyle \delta }$(q1, w, x1x2...xm) ${\displaystyle \longrightarrow }$ (q2, y1y2...yn) 是 GPDA 的转移。

${\displaystyle \delta ^{'}}$(q1, w, x1) ${\displaystyle \longrightarrow }$ (p1, ${\displaystyle \epsilon }$)
${\displaystyle \delta ^{'}}$(p1, ${\displaystyle \epsilon }$, x2) ${\displaystyle \longrightarrow }$ (p2, ${\displaystyle \epsilon }$)
${\displaystyle \vdots }$
${\displaystyle \delta ^{'}}$(pm-1, ${\displaystyle \epsilon }$, xm) ${\displaystyle \longrightarrow }$ (pm, ${\displaystyle \epsilon }$)
${\displaystyle \delta ^{'}}$(pm, ${\displaystyle \epsilon }$, ${\displaystyle \epsilon }$ ) ${\displaystyle \longrightarrow }$ (pm+1, yn)
${\displaystyle \delta ^{'}}$(pm+1, ${\displaystyle \epsilon }$, ${\displaystyle \epsilon }$ ) ${\displaystyle \longrightarrow }$ (pm+2, yn-1)
${\displaystyle \vdots }$
${\displaystyle \delta ^{'}}$(pm+n-1, ${\displaystyle \epsilon }$, ${\displaystyle \epsilon }$ ) ${\displaystyle \longrightarrow }$ (q2, y1)