喬姆斯基正規化



如果產生式具有以下形式,則 CFG 處於喬姆斯基正規化:

  • A → a
  • A → BC
  • S → ε

其中 A、B 和 C是非終結符,而a是終結符。

轉換為喬姆斯基正規化的演算法:

步驟 1 - 如果起始符號S出現在右側,則建立一個新的起始符號S’和一個新的產生式S’→ S

步驟 2 - 刪除空產生式。(使用前面討論的空產生式刪除演算法)

步驟 3 - 刪除單元產生式。(使用前面討論的單元產生式刪除演算法)

步驟 4 - 將每個產生式A → B1…Bn(其中n > 2)替換為A → B1C,其中C → B2 …Bn。對右側具有兩個或多個符號的所有產生式重複此步驟。

步驟 5 - 如果任何產生式的右側具有A → aB的形式(其中 a 是終結符,而A、B是非終結符),則將該產生式替換為A → XBX → a。對所有具有A → aB形式的產生式重複此步驟。

問題

將以下 CFG 轉換為 CNF

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

解答

(1) 由於S出現在 RHS,我們新增一個新狀態S0,並將S0→S新增到產生式集合中,它變成:

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

(2) 現在我們將刪除空產生式:

B → ∈ 和 A → ∈

刪除 B → ε 後,產生式集合變為:

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

刪除 A → ∈ 後,產生式集合變為:

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

(3) 現在我們將刪除單元產生式。

刪除 S → S 後,產生式集合變為:

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

刪除 S0→ S 後,產生式集合變為:

S0→ ASA | aB | a | AS | SA, S→ ASA | aB | a | AS | SA

A → B | S, B → b

刪除 A→ B 後,產生式集合變為:

S0 → ASA | aB | a | AS | SA, S→ ASA | aB | a | AS | SA

A → S | b

B → b

刪除 A→ S 後,產生式集合變為:

S0 → ASA | aB | a | AS | SA, S→ ASA | aB | a | AS | SA

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

(4) 現在我們將找出 RHS 中超過兩個變數的情況

這裡,S0→ ASA,S → ASA,A→ ASA 違反了 RHS 中兩個以上非終結符的限制。

因此,我們將應用步驟 4 和步驟 5 以獲得以下最終產生式集合,它處於 CNF:

S0→ AX | aB | a | AS | SA

S→ AX | aB | a | AS | SA

A → b |AX | aB | a | AS | SA

B → b

X → SA

(5) 我們必須更改產生式 S0→ aB,S→ aB,A→ aB

最終產生式集合變為:

S0→ AX | YB | a | AS | SA

S→ AX | YB | a | AS | SA

A → b A → b |AX | YB | a | AS | SA

B → b

X → SA

Y → a

廣告