確定下推自動機

自動機理論中,確定下推自動機(英語:Deterministic pushdown automaton,縮寫:DPDA)是可以使用了持有數據的確定有限狀態自動機。術語「下推」來自原型機械自動機物理上接觸穿孔卡片來閱讀其內容的下推動作。術語「確定下推自動機」當前指稱識別確定上下文無關語言的抽象計算設備。

確定下推自動機是減弱版本的下推自動機

定義

編輯

一個下推自動機(PDA) M 可以定義為一個 7-元組:

  這裏的

  •   是狀態的有限集合
  •   是輸入字母表的有限集合
  •   是棧字母表的有限集合
  •   是開始狀態,是   的元素
  •   是初始棧符號,是   的元素
  •   是最終狀態的集合,是   的子集
  •   是有限轉移(transition)關係  

M 是確定的,如果它滿足下列兩個條件:

  • 對於任何  ,集合   有最多一個元素。
  • 對於任何  ,如果  ,則   對於所有  

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

性質

編輯

傑霍·賽尼澤格英語Géraud Sénizergues證明了確定 PDA 的等價問題(即給定兩個確定 PDA A 和 B,L(A)=L(B) 嗎?)是可決定的。對非確定 PDA 這個問題是不可決定的。