PlanarG's blog

Pushdown Automata

下推自动机可以看作是 NFA 加入栈后的拓展版本。与 NFA 相比，PDA 的定义中多了一个“栈”的概念，一个 PDA 由六元组 $(Q, \Sigma, \Gamma, \delta, q_0, F)$ 组成。其中：

• $Q, \Sigma, q_0, F$​ 与 NFA 的定义完全一致，它们分别表示状态，字符集，起始节点，接受节点集。
• $\Gamma$ 是栈字符集，它规定了栈中的每个元素可能是什么。我们常常通过往栈中压入或者弹出一个 $ 来确保当前栈是空的。
• $\delta$ 同样是转移函数，但它与 NFA 的区别是引入了栈的状态。$\delta$ 函数接受当前状态、当前栈顶以及一个字符（当然，可以是空串 $\epsilon$），它的输出是一个目标节点以及对当前栈的操作（不从栈顶读字符并压入一个字符、弹出一个字符、更改栈顶字符或者保持栈不动）。更为形式化地说，$\delta$ 的定义是 $Q\times \Sigma_{\epsilon}\times \Gamma_{\epsilon}\to Q\times \Gamma_{\epsilon}$​（输入栈顶即将被替换的那个字符，输出新的栈顶）。