Automata Theory 简明教程

PDA & Context-Free Grammar

如果一个语法 G 是无上下文的，我们可以构建一个等效的非确定性 PDA，它接受由无上下文语法 G 生成的语言。可以为语法 G 构建一个解析器。

另外，如果 P 是下推机，则可以构建一个等效的无上下文语法 G，其中

L(G) = L(P)

在接下来的两个主题中，我们将讨论如何从 PDA 转换为 CFG，反之亦然。

Input - 一个 CFG，G = (V, T, P, S)

Output − 等价的 PDA，P = (Q, ∑, S, δ, q0, I, F)

Step 1 − 将 CFG 的产生式转换成 GNF。

Step 2 − PDA 将只有唯一状态 {q}。

Step 3 − CFG 的起始符号将是 PDA 中的起始符号。

Step 4 − CFG的所有非终结符号将是 PDA 的栈符号，且 CFG 的所有终结符号将是 PDA 的输入符号。

Step 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, ε )}

Input - 一个 CFG，G = (V, T, P, S)

Output − 等价的 PDA，P = (Q, ∑, S, δ, q0, I, F)，其中语法 G 的非终结符为 {Xwx | w,x ∈ Q}，开始状态为 Aq0,F。

Step 1 − 对于 Q 中的每个 w、x、y、z，S 中的 m 以及 ∑ 中的 a、b，如果 δ (w, a, ε) 包含 (y, m) 且 (z, b, m) 包含 (x, ε) ，则在语法 G 中添加产生式规则 Xwx → a Xyzb。

Step 2 - 对于任意 Q 中的 w、x、y、z，在语法 G 中添加产生式 Xwx → XwyXyx。

Step 3 - 对于 Q 中的 w，在语法 G 中添加产生式 Xww → ε。