確定下推自動機

在自動機理論中，確定性下推自動機（DPDA或DPA）是下推自動機的變體。 確定性下推自動機類接受確定性無上下文語言，這是無上下文語言的適當子集。

機器轉換基於當前狀態和輸入符號，以及堆疊的當前最頂部符號。 堆疊中較低的符號不可見，並且沒有立即生效。 機器動作包括推動，彈出或更換堆疊頂部。 確定性下推自動機對於輸入符號，狀態和頂部堆疊符號的相同組合最多具有一個合法轉換。 這是它與非確定性下推自動機的不同之處。

基本介紹

• 中文名：確定下推自動機
• 外文名：Deterministic pushdown automaton

語言

如果L（A）是PDA A接受的語言，若且唯若從初始配置有單個計算直到屬於L（A）的所有字元串的接受時，DPDA也可以接受它。如果L（A）可以被PDA接受，那么它是一種無上下文的語言，如果它可以被DPDA接受，那么它就是一種確定性的無上下文語言。

並非所有無上下文的語言都是確定性的。這使得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，等價是不可判定的。