CFG 簡化



在 CFG 中,可能會發生並非所有產生式規則和符號都用於字串的推導。此外,可能存在一些空產生式和單元產生式。消除這些產生式和符號稱為 **CFG 的簡化**。簡化主要包括以下步驟:

  • CFG 的化簡
  • 移除單元產生式
  • 移除空產生式

CFG 的化簡

CFG 分兩個階段進行化簡:

**階段 1** - 從 CFG **G** 推匯出等價文法 **G’**,使得每個變數都推匯出某個終結符串。

**推導過程** -

步驟 1 - 包含所有推匯出某個終結符的符號 **W1**,並初始化 **i=1**。

步驟 2 - 包含所有推匯出 **Wi** 的符號 **Wi+1**。

步驟 3 - 增加 **i** 並重復步驟 2,直到 **Wi+1 = Wi**。

步驟 4 - 包含所有包含 **Wi** 的產生式規則。

**階段 2** - 從 CFG **G’** 推匯出等價文法 **G”**,使得每個符號都出現在某個句型中。

**推導過程** -

步驟 1 - 將開始符號包含在 **Y1** 中,並初始化 **i = 1**。

步驟 2 - 包含所有可以從 **Yi** 推匯出的符號 **Yi+1**,幷包含所有已應用的產生式規則。

步驟 3 - 增加 **i** 並重復步驟 2,直到 **Yi+1 = Yi**。

問題

找到一個與文法 G 等價的化簡文法,G 具有產生式規則 P:S → AC | B,A → a,C → c | BC,E → aA | e

解答

**階段 1** -

T = { a, c, e }

根據規則 A → a,C → c 和 E → aA,W1 = { A, C, E }

根據規則 S → AC,W2 = { A, C, E } U { S }

W3 = { A, C, E, S } U ∅

由於 W2 = W3,我們可以推匯出 G’ 為:

G’ = { { A, C, E, S }, { a, c, e }, P, {S}}

其中 P:S → AC,A → a,C → c ,E → aA | e

**階段 2** -

Y1 = { S }

根據規則 S → AC,Y2 = { S, A, C }

根據規則 A → a 和 C → c,Y3 = { S, A, C, a, c }

Y4 = { S, A, C, a, c }

由於 Y3 = Y4,我們可以推匯出 G” 為:

G” = { { A, C, S }, { a, c }, P, {S}}

其中 P:S → AC,A → a,C → c

移除單元產生式

任何形式為 A → B 的產生式規則,其中 A、B ∈ 非終結符,稱為 **單元產生式**。

移除過程 -

**步驟 1** - 為了移除 **A → B**,每當 **B → x** 出現在文法中時,將產生式 **A → x** 新增到文法規則中。[x ∈ 終結符,x 可以為空]

**步驟 2** - 從文法中刪除 **A → B**。

**步驟 3** - 重複步驟 1,直到所有單元產生式都被移除。

問題

從以下內容中移除單元產生式:

S → XY,X → a,Y → Z | b,Z → M,M → N,N → a

**解答** -

文法中有 3 個單元產生式:

Y → Z,Z → M,和 M → N

首先,我們將移除 M → N。

由於 N → a,我們新增 M → a,並移除 M → N。

產生式集變為

S → XY,X → a,Y → Z | b,Z → M,M → a,N → a

現在我們將移除 Z → M。

由於 M → a,我們新增 Z→ a,並移除 Z → M。

產生式集變為

S → XY,X → a,Y → Z | b,Z → a,M → a,N → a

現在我們將移除 Y → Z。

由於 Z → a,我們新增 Y→ a,並移除 Y → Z。

產生式集變為

S → XY,X → a,Y → a | b,Z → a,M → a,N → a

現在 Z、M 和 N 不可到達,因此我們可以移除它們。

最終的 CFG 不包含單元產生式:

S → XY,X → a,Y → a | b

移除空產生式

在 CFG 中,非終結符 **‘A’** 是一個可空變數,如果存在產生式 **A → ε** 或存在一個從 **A** 開始並最終以

ε 結束的推導:A → .......… → ε

移除過程

**步驟 1** - 找出推匯出 ε 的可空非終結符變數。

**步驟 2** - 對於每個產生式 **A → a**,構造所有產生式 **A → x**,其中 **x** 是從 **‘a’** 中移除一個或多個來自步驟 1 的非終結符獲得的。

**步驟 3** - 將原始產生式與步驟 2 的結果結合起來,並移除 **ε - 產生式**。

問題

從以下內容中移除空產生式:

S → ASA | aB | b,A → B,B → b | ∈

**解答** -

有兩個可空變數:**A** 和 **B**

首先,我們將移除 B → ε。

移除 **B → ε** 後,產生式集變為:

S→ASA | aB | b | a, A ε B| b | &epsilon, B → b

現在我們將移除 A → ε。

移除 **A → ε** 後,產生式集變為:

S→ASA | aB | b | a | SA | AS | S, A → B| b, B → b

這是最終不包含空轉換的產生式集。

廣告