PDA#

有栈用了

定义是一个七元组：

• $Q$ 是一个有限的状态集合
• $\Sigma$ 是一个有限的输入符号集合
• $\Gamma$ 是一个有限的栈符号集合
• $\delta$ 是一个状态转移函数，定义为 $\delta: Q \times (\Sigma \cup \{\epsilon\}) \times \Gamma \to P(Q \times \Gamma^*)$，其中 $P$ 表示幂集
• $q_0 \in Q$ 是初始状态
• $Z_0 \in \Gamma$ 是初始栈符号
• $F \subseteq Q$ 是接受状态集合

绘制PDA#

状态转移条件形如$a, b / ab$，表示消费输入符号$a$，且当前栈顶符号为$b$时，然后将$a$压入栈中

• $a, b / \epsilon$，表示消费输入符号$a$，且当前栈顶符号为$b$时，然后将栈顶符号$b$弹出
• $a, b / b$，表示消费输入符号$a$，且当前栈顶符号为$b$时，不进行任何操作，保持栈顶符号$b$不变
• $\epsilon, b / b$，表示不消费任何符号，且当前栈顶符号为$b$时，不进行任何操作，保持栈顶符号$b$不变

PDA的接受方式#

1. 终态接受：当输入字符串被完全消费，且PDA处于一个接受状态
2. 空栈接受：当输入字符串被完全消费，且PDA的栈为空(栈底$Z_0$也被弹出)

PDA与DPDA#

DPDA是确定性下推自动机，PDA是非确定性下推自动机

相比与PDA，DPDA有以下限制：

1. 对于同一个输入符号，从同一个状态和栈顶符号出发，最多只能有一个转移
2. 如果存在$\epsilon$转移，则不能有任何其他转移(读还是不读输入符号)

DPDA推荐使用终态接受方式，DPDA中终态接受强于空栈接受

一些技巧#

由于PDA只能看见栈顶和当前输入，看不到栈中更下方的符号，因此在设计PDA时，可以自定义栈符号来存储一些结构化信息，例如可以将字母表$\{a,b\}$产生的组合$abb$表示为符号$X_{abb}$，这样就可以在一次转移中看到更多的信息，这个方法还可以用来计数，比如用$A_{n}$表示刚刚已经压入了$n$个$a$，而且还可以用来实现条件分支