在自動機理論中,確定下推自動機(英語: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 這個問題是不可決定的。
|
---|
| | | 每個語言範疇都是其直接上面的範疇的真子集 每個語言範疇內的語言都可以用同一行的文法和自動機表示 |
|