确定下推自动机

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

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

定义

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

${\displaystyle M=(Q,\Sigma ,\Gamma ,q_{0},Z_{0},A,\delta )}$ 这里的

• ${\displaystyle Q}$ 是状态的有限集合
• ${\displaystyle \Sigma }$ 是输入字母表的有限集合
• ${\displaystyle \Gamma }$ 是栈字母表的有限集合
• ${\displaystyle q_{0}}$ 是开始状态，是 ${\displaystyle Q}$ 的元素
• ${\displaystyle Z_{0}}$ 是初始栈符号，是 ${\displaystyle \Gamma }$ 的元素
• ${\displaystyle A}$ 是最终状态的集合，是 ${\displaystyle Q}$ 的子集
• ${\displaystyle \delta }$ 是有限转移(transition)关系 ${\displaystyle Q\times (\Sigma \cup \left\{\epsilon \right\})\times \Gamma \longrightarrow {\mathcal {P}}(Q\times \Gamma ^{*})}$。

M 是确定的，如果它满足下列两个条件:

• 对于任何 ${\displaystyle q\in Q,a\in \Sigma \cup \left\{\epsilon \right\},X\in \Gamma }$，集合 ${\displaystyle \delta (q,a,X)}$ 有最多一个元素。
• 对于任何 ${\displaystyle q\in Q,X\in \Gamma }$，如果 ${\displaystyle \delta (q,\epsilon ,X)\not =\varnothing }$，则 ${\displaystyle \delta (q,a,X)=\varnothing }$ 对于所有 ${\displaystyle a\in \Sigma }$

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

性质

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