下推自动机

理解

1. 具备与上下文无关文法等价的定义语言的能力
2. 看作$\varepsilon$-NFA 和一个栈的结合
3. 它的动作由三个要素决定
   1. 当前 NFA 的状态
   2. 当前的输入符号（或者是$\varepsilon$）
   3. 当前的栈顶符号

运转：

1. 控制器从输入带读入一个符号$a$，栈顶弹出一个栈顶符号$Z$
2. 根据符号$a$，符号$Z$，当前所处的状态进行状态转移并且对栈压入$0$个符号或者一个字符串
   1. 压入$0$个符号意味着弹出操作
   2. 压入符号串意味着压入操作

定义

• PDA 的定义

常用符号：

• 输入带符号：$a,b,\cdots,\varepsilon$
• 栈符号：$X,Y,Z$
• 输入的字符串：$w,x,y,z$
• 栈字符串：$\alpha,\beta$

状态转移函数

1. 接收三个输入参数
   1. 某个状态$q\in Q$
   2. 输入的符号$a(a\in \Sigma \ or \ a = \varepsilon)$
   3. 栈顶符号$X\in \Gamma$
2. $\delta(q,a,X) = \{(p,Y),\cdots\}$
   1. 根据$a$和$X$，将当前状态由$q$转移到$p$
   2. 用$Y$代替栈顶的$X$
      1. $Y=\varepsilon$：弹出
      2. $Y=X$：不变
      3. $Y=Z_1Z_2\cdots Z_k$：弹出$X$，依次压入$Z_k,Z_{k-1},\cdots,Z_2,Z_1$