下推自动机

英语: Pushdown automata, PDA.

下推自动机 (以下简称 PDA) 的工作方式与 NFA 相似, 但支持对栈的压栈(push)和出栈(pop)操作. 栈是 PDA 的内存, 无限大.

因为仅支持压栈和出栈操作, 读取栈顶部元素就意味着需要移除该元素, 并不存在仅读取栈头部元素的操作.

正式定义

一个 PDA 是一个六元组 \((Q, \Sigma, \Gamma, \delta, q_0, F)\), 其中:

\(Q\) 是状态的有限集.
\(\Sigma\) 是由字母表符号组成的有限集.
\(\delta: Q \times \Sigma_\varepsilon \times \Gamma_\varepsilon \rightarrow \mathcal{P}(Q \times \Gamma_\varepsilon)\) 是转移函数. \(\delta(q, a, c) = \{(r_1, d), (r_2, e)\}\)
\(q_0 \in Q\) 是初始状态.
\(F \subseteq Q\) 是接受状态的集合.

其中 \(\Sigma_\varepsilon\) 和 \(\Gamma_\varepsilon\) 的脚标 \(\varepsilon\) 表示该集合包含空字符串.

第一个 \(\Gamma_\varepsilon\) 表示弹出堆栈顶部的元素, 如果为 \(\varepsilon\) 则表示不执行出栈操作. 第二个 \(\Gamma_\varepsilon\) 表示要压入堆栈顶部的元素, 如果为 \(\varepsilon\) 则表示不执行压栈操作.