下推自動機接受



有兩種不同的方法可以定義 PDA 的可接受性。

最終狀態可接受性

在最終狀態可接受性中,當 PDA 讀取完整個字串後處於最終狀態時,PDA 接受一個字串。從起始狀態,我們可以進行最終狀態的移動,並帶有任何堆疊值。只要我們最終處於最終狀態,堆疊值就無關緊要。

對於 PDA (Q, ∑, S, δ, q0, I, F),由最終狀態集 F 接受的語言是:

L(PDA) = {w | (q0, w, I) ⊢* (q, ε, x), q ∈ F}

對於任何輸入堆疊字串x

空堆疊可接受性

在這裡,當 PDA 讀取完整個字串後清空其堆疊時,PDA 接受一個字串。

對於 PDA (Q, ∑, S, δ, q0, I, F),由空堆疊接受的語言是:

L(PDA) = {w | (q0, w, I) ⊢* (q, ε, ε), q ∈ Q}

示例

構造一個接受L = {0n 1n | n ≥ 0}的 PDA

解答

PDA for L

此語言接受 L = {ε, 01, 0011, 000111, ............................. }

在這裡,在這個例子中,‘0’‘1’ 的數量必須相同。

  • 最初,我們將一個特殊的符號‘$’放入空堆疊中。

  • 然後在狀態q2,如果我們遇到輸入 0 並且頂部為空,我們將 0 推入堆疊。這可能會迭代。如果我們遇到輸入 1 並且頂部是 0,我們將彈出此 0。

  • 然後在狀態q3,如果我們遇到輸入 1 並且頂部是 0,我們將彈出此 0。這也可能會迭代。如果我們遇到輸入 1 並且頂部是 0,我們將彈出頂部元素。

  • 如果在堆疊頂部遇到特殊符號 '$',則將其彈出,最終進入接受狀態 q4

示例

構造一個接受 L = { wwR | w = (0+1)* } 的 PDA

解答

PDA for L1

最初,我們將一個特殊的符號 '$' 放入空堆疊中。在狀態q2,正在讀取w。在狀態q3,當每個 0 或 1 與輸入匹配時,它會被彈出。如果給出任何其他輸入,PDA 將進入死狀態。當我們到達特殊符號 '$' 時,我們將進入接受狀態q4

廣告