格雷巴赫正規化 (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) = ∅

Bhanu Priya

更新於: 2021-06-16

1K+ 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習