PDA 與上下文無關文法

如果一個文法G是上下文無關的，我們可以構建一個等價的非確定性 PDA，它接受由上下文無關文法G產生的語言。可以為文法G構建一個解析器。

此外，如果P是一個下推自動機，則可以構造一個等價的上下文無關文法 G，其中

L(G) = L(P)

在接下來的兩個主題中，我們將討論如何從 PDA 轉換為 CFG，反之亦然。

查詢與給定 CFG 對應的 PDA 的演算法

輸入 - 一個 CFG，G = (V, T, P, S)

輸出 - 等價的 PDA，P = (Q, ∑, S, δ, q₀, I, F)

步驟 1 - 將 CFG 的產生式轉換為 GNF。

步驟 2 - PDA 只有一個狀態 {q}。

步驟 3 - CFG 的起始符號將是 PDA 中的起始符號。

步驟 4 - CFG 的所有非終結符將是 PDA 的棧符號，CFG 的所有終結符將是 PDA 的輸入符號。

步驟 5 - 對於每個形如A → aX 的產生式，其中 a 是終結符，A, X 是終結符和非終結符的組合，建立一個轉移δ (q, a, A)。

問題

從以下 CFG 構造一個 PDA。

G = ({S, X}, {a, b}, P, S)

其中產生式為 -

S → XS | ε , A → aXb | Ab | ab

解決方案

令等價的 PDA 為，

P = ({q}, {a, b}, {a, b, X, S}, δ, q, S)

其中 δ -

δ(q, ε , S) = {(q, XS), (q, ε )}

δ(q, ε , X) = {(q, aXb), (q, Xb), (q, ab)}

δ(q, a, a) = {(q, ε )}

δ(q, 1, 1) = {(q, ε )}

查詢與給定 PDA 對應的 CFG 的演算法

輸入 - 一個 CFG，G = (V, T, P, S)

輸出 - 等價的 PDA，P = (Q, ∑, S, δ, q₀, I, F)，使得文法 G 的非終結符為 {X_wx | w,x ∈ Q}，起始狀態為 A_q0,F。

步驟 1 - 對於每個 w, x, y, z ∈ Q, m ∈ S 和 a, b ∈ ∑，如果 δ (w, a, ε) 包含 (y, m) 且 (z, b, m) 包含 (x, ε)，則在文法 G 中新增產生式規則 X_wx → a X_yzb。

步驟 2 - 對於每個 w, x, y, z ∈ Q，在文法 G 中新增產生式規則 X_wx → X_wyX_yx。

步驟 3 - 對於 w ∈ Q，在文法 G 中新增產生式規則 X_ww → ε。