格雷巴赫范式 (GNF) 解释

设 G = (V, T, P, S) 为一个上下文无关文法。如果 P 中的每个产生式都具有如下形式

A -> aa

其中 A ∈ V，a ∈ T，α ∈ V*，则称 G 处于格雷巴赫范式 (GNF)。

示例

S -> aAB | bB A -> aA | a

B -> bB | c

  • 定理 - 设 L 为一个不包含 {ε} 的上下文无关语言。则存在一个 GNF 文法 G，使得 L = L(G)。
  • 引理 1 - 设 L 为一个上下文无关语言。则存在一个下推自动机 M，使得 L = LE(M)。
  • 证明 - 不失一般性，假设 ε 不在 L 中。构造可以稍后修改以包含 ε。

设 G = (V, T, P, S) 为一个上下文无关文法，并且不失一般性地假设 G 处于 GNF。

构造 M = (Q, Σ, Γ, δ, q, Z, F)，其中 -

Q = {q}

Σ = T

Γ = V

Z = S

δ: 对于所有 a ∈ Σ 和 A ∈ Γ，

δ(q, a, A) 包含 (q, y)，如果 A -> ay ∈ P，或者更确切地说 -

δ(q, a, A) = {(q, y) | A -> ay ∈ P 且 y ∈ Γ*}，对于所有 a ∈ Σ 和 A ∈ Γ

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

示例

考虑以下处于 GNF 的上下文无关文法。

S ^ aS S a

构造 M 如下 -

Q = {q}

Σ = T = {a} Γ = V = {S}

Z = S

δ(T a S) = {(T S) (T s)}

δ(q, s, S) = ∅

更新于: 2021-06-16

1K+ 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告