##### 下推自动机 - 下推自动机 - **下推自动机** $\text{PDA}$ 是一种比[[有限自动机]]更强大的[[自动机]], 它通过引入一个栈作为附加的存储空间, 用于存储无限长度的辅助信息, 从而能够识别更复杂的[[上下文无关语言]]. 下推自动机可以定义为一个七元组 $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$, 其中 - $Q$ 有限状态集合 - $\Sigma$ 输入字母表 - $\Gamma$ 栈字母表 - $\delta : Q \times (\Sigma \cup \{\varepsilon\}) \times \Gamma \to \mathcal{P}(Q \times \Gamma^*)$ 状态转移函数 - $q_0 \in Q$ 初始状态 - $Z_0 \in \Gamma$ 初始栈符号 - $F \subseteq Q$ 接受状态集合