在計算理論中解釋非確定性下推自動機。

非確定性下推自動機 (NPDA) 類似於有限自動機 (FA)，但它還有一個堆疊記憶體，可以在其中儲存任意數量的資訊。

讀/寫堆疊記憶體的工作方式是後進先出 (LIFO)。

我們可以用堆疊做什麼？

彈出操作讀取頂部符號並將其從堆疊中刪除；壓入操作將指定的符號寫入堆疊頂部，例如 push(X) 表示將 X 放入堆疊頂部；nop 操作對堆疊不做任何操作。

堆疊符號與輸入帶上使用的“語言”字母不同。

我們從以下開始：

  • 堆疊上只有初始堆疊符號（堆疊上沒有其他內容！）處於控制自動機的起始狀態。

  • 在每一步中，狀態、輸入元素和堆疊中的頂部符號決定下一步（轉換）。

一個轉換步驟包括以下內容：

  • 更改狀態（如 FA）。

  • 從輸入帶上讀取符號並移動到下一個右側符號（如 FA）。

  • 更改堆疊（將符號壓入堆疊/從堆疊彈出符號/堆疊無變化）。

轉換步驟由轉換函式正式定義（通常以轉換指令的形式）。

NPDA 可以描述如下：

  • 一個有限的狀態集 Q（和起始狀態以及接受/最終狀態集）。

  • 一個有限的輸入字母表集 ∑。

  • 一個有限的堆疊字母表集 Γ（和初始堆疊符號 $）。

  • 一組有限的轉換指令（或轉換函式 T）。

T : Q × ∑ ∪ {∧} × Γ → Γ* × Q

或者它可以用下圖所示的“轉換”圖表示：

更新於：2021年6月15日

9K+ 次瀏覽

啟動你的職業生涯

完成課程獲得認證

開始學習
廣告