确定下推自动机

维基百科,自由的百科全书
跳转至: 导航搜索

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

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

定义[编辑]

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

M=(Q,\Sigma,\Gamma,q_0,Z_0,A,\delta) 这里的

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

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

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

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

性质[编辑]

Geraud Senizergues (1998) 证明了确定 PDA 的等价问题(就是给定两个确定 PDA A 和 B,L(A)=L(B) 吗?)是可决定的。对非确定 PDA 这个问题是不可决定的。