下推自动机(Pushdown Automaton)

下推自动机(Pushdown Automaton,PDA)是一种带有栈存储的自动机模型。它在有限状态控制的基础上,配备一个可以压入和弹出符号的栈。每一步转移不仅取决于当前状态和输入符号,还取决于栈顶符号,并可对栈进行修改。栈提供的无界后进先出记忆,使下推自动机的识别能力超越有限自动机。

概述

下推自动机识别的语言类恰好是上下文无关语言,与上下文无关文法一一对应。也就是说,一个语言能被某个下推自动机接受,当且仅当它能由某个上下文无关文法生成。凭借栈的记忆,它能处理需要计数与匹配的结构,例如括号配对语言,这是有限自动机无法完成的。

核心原理

• 栈存储:通过压栈记录已读入但尚未匹配的信息,通过弹栈进行配对与消解。
• 转移依赖栈顶:每步动作由状态、输入符号和栈顶符号共同决定。
• 接受方式:可以按终结状态接受,也可以按空栈接受,两种方式表达能力相同。
• 非确定性更强:非确定下推自动机严格强于确定下推自动机,后者只对应确定性上下文无关语言。

应用场景

下推自动机是编译器语法分析阶段的理论模型。自顶向下和自底向上的语法分析算法,本质上都是在模拟一个下推自动机的运行:用栈保存尚未归约的符号或待展开的产生式。它还用于表达式求值、括号匹配检查以及描述具有嵌套结构的语言。

常见问题

问:下推自动机和图灵机有何区别?答:下推自动机只有一个栈,访问受后进先出限制,识别上下文无关语言;图灵机拥有可任意读写的纸带,能力更强,可识别递归可枚举语言。

问:为什么栈能识别括号匹配而有限自动机不能?答:括号匹配需要记住任意深度的嵌套层数,有限状态无法保存无界计数,而栈的深度可以任意增长。