
- 自動機理論教程
- 自動機理論 - 首頁
- 自動機理論 - 入門
- 自動機理論 - 歷史
- 自動機理論 - 應用
- 自動機理論術語
- 自動機中字串的基礎知識
- 自動機的集合論
- 語言和文法
- 計算理論中的文法
- 由文法生成的語言
- 喬姆斯基文法分類
- 有限自動機
- 確定性有限自動機 (DFA)
- 非確定性有限自動機 (NFA)
- 從 NFA 到 DFA 的轉換
- DFA 的最小化
- Moore 機與 Mealy 機
- DFA 的補集
- 正則表示式
- 自動機中的正則表示式
- 自動機中的 Arden 定理
- 將正則表示式轉換為有限自動機
- 正則文法的泵引理
- 計算理論中的正則集
- 上下文無關文法
- 上下文無關文法 (CFG)
- 上下文無關文法中的二義性
- 上下文無關語言的閉包性質
- 簡化上下文無關文法
- 喬姆斯基正規化 (CNF)
- 格雷巴赫正規化 (GNF)
- 上下文無關文法的泵引理
- 下推自動機
- 下推自動機 (PDA)
- 下推自動機的接受
- 根據 CFG 構造 PDA
- 下推自動機和語法分析
- 圖靈機
- 圖靈機 (TM) 基礎
- 圖靈機接受的語言
- 多磁帶圖靈機
- 多軌跡圖靈機
- 非確定性圖靈機
- 半無限帶圖靈機
- 線性界限自動機 (LBA)
- 可計算性和不可判定性
- 圖靈語言的可判定性
- 不可判定語言
- 圖靈機停機問題
- 計算理論中的 Rice 定理
- Post 對應問題 (PCP)
- 自動機理論資源
- 自動機理論 - 快速指南
- 自動機理論 - 資源
- 自動機理論 - 討論
喬姆斯基正規化
如果產生式具有以下形式,則 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 → XB和X → 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