跳至內容

確定下推自動機

維基百科,自由的百科全書

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

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

定義

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

這裏的

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

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

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

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

性質

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