Pushdown Automaton

释义 Definition

下推自动机（PDA）：一种在有限自动机的基础上加入栈（stack）作为辅助存储的计算模型，常用于描述和识别上下文无关语言（context-free languages），例如匹配括号、处理嵌套结构等。（也常见缩写：PDA）

发音 Pronunciation (IPA)

/ˈpʊʃˌdaʊn ˌɔːtəˈmætən/

例句 Examples

A pushdown automaton can recognize balanced parentheses.
下推自动机可以识别括号是否成对匹配。

Unlike a finite automaton, a pushdown automaton uses a stack to handle nested structures in context-free grammars.
与有限自动机不同，下推自动机通过栈来处理上下文无关文法中的嵌套结构。

词源 Etymology

“pushdown”源于“push（压入）+ down（向下）”，形象描述了把符号压入栈顶的操作；“automaton”来自希腊语 automatos，意为“自发运作的东西、自动装置”。合起来指“带有入栈/出栈能力的自动机”。

相关词 Related Words

• Stack
• Finite Automaton
• Context-Free Grammar
• Context-Free Language
• Nonterminal
• Transition
• Deterministic
• Nondeterministic
• Parser

文学与经典著作 Literary Works

• Introduction to Automata Theory, Languages, and Computation（Hopcroft, Motwani, Ullman）——在自动机与形式语言章节系统介绍 pushdown automaton。
• Introduction to the Theory of Computation（Michael Sipser）——用于讲解上下文无关语言与PDA的等价性与应用。
• Compilers: Principles, Techniques, and Tools（Aho, Lam, Sethi, Ullman，“龙书”）——在语法分析（parsing）背景下讨论与栈相关的自动机思想与上下文无关语法。