
- 自動機理論教程
- 自動機理論 - 首頁
- 自動機理論 - 入門
- 自動機理論 - 歷史
- 自動機理論 - 應用
- 自動機理論術語
- 自動機中字串的基礎知識
- 自動機的集合論
- 語言和文法
- 計算理論中的文法
- 由文法生成的語言
- 喬姆斯基文法分類
- 有限自動機
- 確定性有限自動機 (DFA)
- 非確定性有限自動機 (NFA)
- 從 NFA 到 DFA 的轉換
- DFA 的最小化
- Moore 機與 Mealy 機
- DFA 的補集
- 正則表示式
- 自動機中的正則表示式
- 自動機中的 Arden 定理
- 將正則表示式轉換為有限自動機
- 正則文法的泵引理
- 計算理論中的正則集
- 上下文無關文法
- 上下文無關文法 (CFG)
- 上下文無關文法中的二義性
- 上下文無關語言的封閉性
- 簡化上下文無關文法
- 喬姆斯基正規化 (CNF)
- 格雷巴赫正規化 (GNF)
- 上下文無關文法的泵引理
- 下推自動機
- 下推自動機 (PDA)
- 下推自動機接受
- 從 CFG 構造 PDA
- 下推自動機和解析
- 圖靈機
- 圖靈機 (TM) 基礎
- 圖靈機接受的語言
- 多磁帶圖靈機
- 多軌跡圖靈機
- 非確定性圖靈機
- 半無限磁帶圖靈機
- 線性有界自動機 (LBA)
- 可計算性和不可判定性
- 圖靈語言的可判定性
- 不可判定語言
- 圖靈機停機問題
- 計算理論中的 Rice 定理
- Post 對應問題 (PCP)
- 自動機理論資源
- 自動機理論 - 快速指南
- 自動機理論 - 資源
- 自動機理論 - 討論
下推自動機接受
有兩種不同的方法可以定義 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
解答

此語言接受 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
解答

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