下推自动机

“无限状态自动机”：由无穷多个有限状态自动机组成的自动机 $L=\sum_{n=0}^\infty\bm 0^n\bm 1^n=\{0^n1^n|n\geq 0\}$

# 下推自动机(Pushdown Automata, PDA)形式定义

PDA

PDA为一个七元组 $P$ ：

$P=(Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$

$Q$ ：有穷状态集
$\Sigma$ ：字母表（有穷输入符号集）
$\Gamma$ ：有穷栈符号集
$\delta$ ：状态转移函数， $\delta:Q\times(\Sigma\cup\{\varepsilon\})\rightarrow 2^{Q\times\Gamma^*}$
$q_0$ ：初始状态， $q_0\in Q$
$Z_0$ ：栈底符号， $Z_0\in\Gamma-\Sigma$
$F$ ：终结状态集（接受状态集）， $F\subseteq Q$

# 定义PDA的动作（状态转移函数详解）

对PDA的当前状态 $q\in Q$ 、输入字符 $a\in\Sigma$ 、当前栈顶符号 $Z$ ，状态转移函数：

$\delta(q,a,Z)=\{(p,\beta)|p\in Q,\beta\in\Gamma^*\}$

表示PDA的状态转移为 $p\in Q$ 、栈顶符号修改为字符串 $\beta$ ，且转移过程是非确定的。每一个状态的状态转移图表示为：

栈顶的一个符号 $Z$ 修改为字符串 $\beta$ $\rightarrow$ 弹出栈顶符号后再压入多个符号
栈顶的一个符号 $Z$ 修改为空串 $\varepsilon$ $\rightarrow$ 只弹出栈顶符号不压入符号

由定义可知，PDA还具有空转移能力：

$\delta(q,\varepsilon,Z)=\{(p,\beta)|p\in Q,\beta\in\Gamma^*\}$

每一个状态的状态转移图表示为：

综合得一次状态转移的状态转移图：

# 例：语言 $L=\sum_{n=0}^\infty\bm 0^n\bm 1^n=\{0^n1^n|n\geq 0\}$ 的PDA

# PDA的瞬时描述

PDA的瞬时描述(Instantaneous Description, ID)定义为：

$(q,w,\gamma)\in Q\times\Sigma^*\times\Gamma^*$

表示此时PDA处于状态 $q$ ，剩余输入串为 $w$ ，栈内符号串为 $\gamma$ 。

# ID的转移

若PDA $P$ 某一步状态转移 $(p,\beta)\in\delta(q,a,Z)$ ，则这一步PDA的状态将由 $(q,aw,Z\alpha)$ 变为 $(p,w,\beta\alpha)$ ，称为ID的转移，记为 $\vdash_P$ ：

$(p,\beta)\in\delta(q,a,Z)\Leftrightarrow(q,aw,Z\alpha)\vdash_P(p,w,\beta\alpha)$

进一步，对于瞬时描述 $I$ 、 $J$ 、 $K$ ，可递归定义 $\vdash_P^*$ ：

$\begin{aligned} &I\vdash_P^*I\\ &I\vdash_PJ\wedge J\vdash_P^*K\Rightarrow I\vdash_P^*K\\ \end{aligned}$

$P$ 已知时可省略记为 $\vdash$ 和 $\vdash^*$ 。

# PDA的性质

# PDA一次状态转移不会用到输入字符之后的部分和栈顶符号之下的部分

$(q,x,\alpha)\vdash_P^*(p,y,\beta)\Rightarrow(q,xw,\alpha\gamma)\vdash_P^*(p,yw,\beta\gamma)$

# PDA多次状态转移不会用到输入字符之后的部分（但是可能会用到栈顶符号之下的部分）

$(\forall w\in\Sigma^*)(q,xw,\alpha\gamma)\vdash_P^*(p,yw,\beta\gamma)\Rightarrow(q,x,\alpha)\vdash_P^*(p,y,\beta)$

# PDA的语言

对于一个PDA $P=(Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ ，定义了两种接收语言的方式。

# $\bm L(P)$ ：以终态方式接收的语言

这种语言中的字符串读取结束时可以让PDA运行到接受状态：

$\bm L(P)=\{w|(q_0,w,Z_0)\vdash_P^*(p,\varepsilon,\gamma),p\in F\}$

# $\bm N(P)$ ：以空栈方式接收的语言

这种语言中的字符串读取结束时可以让PDA的栈底符号弹出（栈弹空，使PDA无法正常运行）：

$\bm L(P)=\{w|(q_0,w,Z_0)\vdash_P^*(p,\varepsilon,\varepsilon),p\in F\}$

以空栈方式接收的语言有时可以让PDA的设计更加简单。

# 终态方式和空栈方式的等价性(未完成)

$(\forall L)P_F$

Yin的笔记本

下推自动机