[科普中国]-确定下推自动机

在自动机理论中，确定性下推自动机（DPDA或DPA）是下推自动机的变体。 确定性下推自动机类接受确定性无上下文语言，这是无上下文语言的适当子集。

机器转换基于当前状态和输入符号，以及堆栈的当前最顶部符号。 堆栈中较低的符号不可见，并且没有立即生效。 机器动作包括推动，弹出或更换堆叠顶部。 确定性下推自动机对于输入符号，状态和顶部堆栈符号的相同组合最多具有一个合法转换。 这是它与非确定性下推自动机的不同之处。

语言如果L（A）是PDA A接受的语言，当且仅当从初始配置有单个计算直到属于L（A）的所有字符串的接受时，DPDA也可以接受它。如果L（A）可以被PDA接受，那么它是一种无上下文的语言，如果它可以被DPDA接受，那么它就是一种确定性的无上下文语言1。

并非所有无上下文的语言都是确定性的。这使得DPDA成为比PDA更严格的设备。例如，0和1字母表上偶数长度的回文语言具有无上下文语法S→0S0 | 1S1 | ε。如果不首先读取其所有字母，则无法解析该语言的任意字符串，这意味着下推自动机必须尝试替代状态转换以适应半解析字符串的不同可能长度。

将DPDA限制为单一状态会减少接受LL（1）语言的语言类别。对于PDA，此限制对接受的语言类别没有影响。

属性关闭确定性无上下文语言的闭包属性（由最终状态的确定性PDA接受）与无上下文语言截然不同。 作为一个例子，他们（有效地）在互补下关闭，但在联盟下没有关闭。 为了证明确定性PDA接受的语言的补充也被确定性PDA接受是棘手的。原则上，必须避免无限的计算。

作为互补的结果，确定性PDA是否接受其输入字母表中的所有单词，通过测试其空虚的补充是可判定的。 这对于无上下文的语法是不可能的（因此不适用于一般的PDA）。

等价问题Geraud Senizergues（1997）证明确定性PDA的等价问题（即给定两个确定性的PDA A和B，L（A）= L（B））是可判定的，证明他获得了2002年哥德尔奖。 对于不确定性的PDA，等价是不可判定的。

本词条内容贡献者为:

李嘉骞 - 博士 - 同济大学