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 → ε。