下推自動機介紹

PDA 的基本結構

下推自動機是一種以類似我們為正則文法設計 DFA 的方式實現上下文無關文法的方法。DFA 可以記住有限數量的資訊，但 PDA 可以記住無限數量的資訊。

基本上，下推自動機是 -

"有限狀態機" + "一個棧"

下推自動機具有三個組成部分 -

• 輸入帶，
• 控制單元，以及
• 一個無限大小的棧。

棧指標掃描棧頂符號。

棧執行兩個操作 -

• 壓棧 - 在頂部新增一個新符號。

• 出棧 - 讀取並刪除頂部符號。

PDA 可能會也可能不會讀取輸入符號，但它必須在每次轉換中讀取棧頂。

PDA 可以正式描述為一個 7 元組 (Q, ∑, S, δ, q₀, I, F) -

• Q 是有限數量的狀態

• ∑ 是輸入字母表

• S 是棧符號

• δ 是轉移函式：Q × (∑ ∪ {ε}) × S × Q × S*

• q₀ 是初始狀態 (q₀ ∈ Q)

• I 是初始棧頂符號 (I ∈ S)

• F 是一個接受狀態集 (F ∈ Q)

下圖顯示了 PDA 從狀態 q₁ 到狀態 q₂ 的轉換，標記為 a,b → c -

這意味著在狀態 q₁，如果我們遇到一個輸入字串 'a' 並且棧頂符號是 'b'，那麼我們彈出 'b'，將 'c' 推入棧頂並移動到狀態 q₂。

與 PDA 相關的術語

瞬時描述

PDA 的瞬時描述 (ID) 由一個三元組 (q, w, s) 表示，其中

• q 是狀態

• w 是未消耗的輸入

• s 是棧內容

旋轉門符號

“旋轉門”符號用於連線表示 PDA 一次或多次移動的 ID 對。轉換過程由旋轉門符號“⊢”表示。

考慮一個 PDA (Q, ∑, S, δ, q₀, I, F)。轉換可以用以下旋轉門符號數學表示 -

(p, aw, Tβ) ⊢ (q, w, αb)

這意味著在從狀態 p 到狀態 q 進行轉換時，輸入符號 'a' 被消耗，並且棧頂 'T' 被新字串 'α' 替換。

注意 - 如果我們想要 PDA 的零次或多次移動，我們必須為此使用符號 (⊢*)。