查看“︁确定下推自动机”︁的源代码

在[[自动机]]理论中，'''确定下推自动机'''（{{lang-en|Deterministic pushdown automaton}}，縮寫：'''DPDA'''）是可以使用了持有数据的[[堆栈|栈]]的[[确定有限状态自动机]]。术语“下推”来自原型机械自动机物理上接触[[穿孔卡片]]来阅读其内容的下推动作。术语“确定下推自动机”当前指称识别[[确定上下文无关语言]]的抽象计算设备。 

'''确定下推自动机'''是减弱版本的[[下推自动机]]。

== 定义 ==

一个下推自动机(PDA) ''M'' 可以定义为一个 7-元组:

<math>M=(Q,\Sigma,\Gamma,q_0,Z_0,A,\delta)</math>
这里的
*<math>Q</math> 是状态的有限集合
*<math>\Sigma</math> 是输入字母表的有限集合
*<math>\Gamma</math> 是栈字母表的有限集合
*<math>q_0</math> 是开始状态，是 <math>Q</math> 的元素 
*<math>Z_0</math> 是初始栈符号，是 <math>\Gamma</math> 的元素
*<math>A</math> 是最终状态的集合，是 <math>Q</math> 的子集
*<math>\delta</math> 是有限转移(transition)关系 <math>Q \times ( \Sigma \cup \left \{ \epsilon \right \} ) \times \Gamma \longrightarrow \mathcal{P}(Q \times \Gamma ^{*})</math>。

M  是确定的，如果它满足下列两个条件:
* 对于任何 <math>q \in Q, a \in \Sigma \cup \left \{ \epsilon \right \}, X \in \Gamma</math>，集合 <math>\delta(q,a,X)</math> 有最多一个元素。
*对于任何 <math>q \in Q, X \in \Gamma</math>，如果 <math>\delta(q, \epsilon, X) \not= \varnothing</math>，则 <math>\delta(q,a,X) = \varnothing</math> 对于所有 <math>a \in \Sigma</math>

有两种可能的接受标准: “空栈”接受和“最终状态”接受。对于确定下推自动机这两种接受是不等价的(尽管对于非确定下推自动机是等价的)。被空栈接受的语言是被最终状态接受的语言，同时满足没有在语言中的串是在语言中的其他串的前缀。

== 性质 ==
{{le|傑霍·賽尼澤格|Géraud Sénizergues}}证明了确定 PDA 的等价问题（即给定两个确定 PDA A 和 B，L(A)=L(B) 吗？）是可决定的。对非确定 PDA 这个问题是不可决定的。

{{形式语言与形式文法}}
[[Category:自动机]]
[[Category:编译原理]]