在自动机理论中,确定下推自动机(英语:Deterministic pushdown automaton,缩写:DPDA)是可以使用了持有数据的栈的确定有限状态自动机。术语“下推”来自原型机械自动机物理上接触穿孔卡片来阅读其内容的下推动作。术语“确定下推自动机”当前指称识别确定上下文无关语言的抽象计算设备。
确定下推自动机是减弱版本的下推自动机。
定义
一个下推自动机(PDA) M 可以定义为一个 7-元组:
这里的
是状态的有限集合
是输入字母表的有限集合
是栈字母表的有限集合
是开始状态,是
的元素
是初始栈符号,是
的元素
是最终状态的集合,是
的子集
是有限转移(transition)关系
。
M 是确定的,如果它满足下列两个条件:
- 对于任何
,集合
有最多一个元素。
- 对于任何
,如果
,则
对于所有 ![{\displaystyle a\in \Sigma }](https://wikimedia.org/api/rest_v1/media/math/render/svg/69a485a3b32b5e024b7b34f5e59c42e3d60337a2)
有两种可能的接受标准: “空栈”接受和“最终状态”接受。对于确定下推自动机这两种接受是不等价的(尽管对于非确定下推自动机是等价的)。被空栈接受的语言是被最终状态接受的语言,同时满足没有在语言中的串是在语言中的其他串的前缀。
性质
杰霍·赛尼泽格证明了确定 PDA 的等价问题(即给定两个确定 PDA A 和 B,L(A)=L(B) 吗?)是可决定的。对非确定 PDA 这个问题是不可决定的。
|
---|
| | | 每个语言范畴都是其直接上面的范畴的真子集 每个语言范畴内的语言都可以用同一行的文法和自动机表示 |
|