確定下推自動機

在自動機理論中，確定下推自動機（英語：Deterministic pushdown automaton，縮寫：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$

有兩種可能的接受標準: 「空棧」接受和「最終狀態」接受。對於確定下推自動機這兩種接受是不等價的(儘管對於非確定下推自動機是等價的)。被空棧接受的語言是被最終狀態接受的語言，同時滿足沒有在語言中的串是在語言中的其他串的前綴。

性質

傑霍·賽尼澤格證明了確定 PDA 的等價問題（即給定兩個確定 PDA A 和 B，L(A)=L(B) 嗎？）是可決定的。對非確定 PDA 這個問題是不可決定的。