解释 Greibach 范式 (GNF)

令 G = (V, T, P, S) 为 CFL。如果 P 中的每个产生式都具有以下形式

A -> aa

如果 A 在 V 中，a 在 T 中，a 在 V* 中，则称 G 为 Greibach 范式 (GNF)。

示例

S -> aAB | bB A -> aA | 一种

B -> bB | C

• 定理 - 让 L 是不包含 {s} 的 CFL。那么存在一个 GNF 文法 G 使得 L = L(G)。

• 引理 1 - 让 L 成为 CFL。那么存在一个 PDA M 使得 L = LE(M)。

• 证明 - 不失一般性地假设 s 不在 L 中。该构造可以修改为稍后包含。

设 G = (V, T, P, S) 是一个 CFG，并且不失一般性地假设 G 在 GNF 中。

构造 M = (Q, E, r, 5, q, z, 0) 其中 -

Q = {q}

E = T

r = V

z = S

5：对于 E 中的所有 a 和 r 中的 A，

5(q, a, A) 包含 (q, y) 如果 A -> ay 在 P 中或更确切地说 -

5(q, a, A) = {(q, y) | A -> ay 在 P 中，y 在 r*} 中，因为 E 中的所有 a 和 r 中的 A

对于 E* 中的给定字符串 x，M 将尝试用 G 模拟 x 的最左推导。

示例

考虑以下 GNF 中的 CFG。

S ^ aS a

构造 M 如下 -

Q = {q}

E = T = {a} r = V = {S}

z = S

5(T a S) = {(TS) (T s)}

5(q, s, S) = 0