
- 自動機理論教程
- 自動機理論 - 首頁
- 自動機理論 - 入門
- 自動機理論 - 歷史
- 自動機理論 - 應用
- 自動機理論術語
- 自動機中字串的基礎
- 自動機的集合論
- 語言和文法
- 計算理論中的文法
- 由文法生成的語言
- 喬姆斯基文法分類
- 有限自動機
- 確定性有限自動機 (DFA)
- 非確定性有限自動機 (NFA)
- 從 NFA 到 DFA 的轉換
- DFA 的最小化
- 穆爾機與米利機
- DFA 的補集
- 正則表示式
- 自動機中的正則表示式
- 自動機中的 Arden 定理
- 將正則表示式轉換為有限自動機
- 正則文法的抽運引理
- 計算理論中的正則集
- 上下文無關文法
- 上下文無關文法 (CFG)
- 上下文無關文法中的二義性
- 上下文無關語言的封閉性
- 簡化上下文無關文法
- 喬姆斯基正規化 (CNF)
- 格雷巴赫正規化 (GNF)
- 上下文無關文法的抽運引理
- 下推自動機
- 下推自動機 (PDA)
- 下推自動機的接受
- 從 CFG 構造 PDA
- 下推自動機和語法分析
- 圖靈機
- 圖靈機 (TM) 基礎
- 圖靈機接受的語言
- 多磁帶圖靈機
- 多軌跡圖靈機
- 非確定性圖靈機
- 半無限帶圖靈機
- 線性界限自動機 (LBA)
- 可計算性和不可判定性
- 圖靈語言的可判定性
- 不可判定語言
- 圖靈機停機問題
- 計算理論中的 Rice 定理
- Post 對應問題 (PCP)
- 自動機理論資源
- 自動機理論 - 快速指南
- 自動機理論 - 資源
- 自動機理論 - 討論
格雷巴赫正規化
如果產生式具有以下形式,則 CFG 處於格雷巴赫正規化:
A → b
A → bD1…Dn
S → ε
其中 A、D1、....、Dn是非終結符,b 是終結符。
將 CFG 轉換為格雷巴赫正規化的演算法
步驟 1 - 如果起始符號 S 出現在某個右側,則建立一個新的起始符號 S’ 和一個新的產生式 S’ → S。
步驟 2 - 刪除空產生式。(使用前面討論的空產生式刪除演算法)
步驟 3 - 刪除單元產生式。(使用前面討論的單元產生式刪除演算法)
步驟 4 - 刪除所有直接和間接的左遞迴。
步驟 5 - 對產生式進行適當的替換,將其轉換為 GNF 的正確形式。
問題
將以下 CFG 轉換為 CNF
S → XY | Xn | p
X → mX | m
Y → Xn | o
解決方案
這裡,S 沒有出現在任何產生式的右側,並且產生式規則集中沒有單元或空產生式。因此,我們可以跳過步驟 1 到步驟 3。
步驟 4
現在替換
S → XY | Xo | p 中的
X 為
mX | m
我們得到
S → mXY | mY | mXo | mo | p。
並且替換
Y → Xn | o 中的
X 為
X → mX | m
我們得到
Y → mXn | mn | o 的右側。
向產生式集中添加了兩個新的產生式 O → o 和 P → p,然後我們得到了最終的 GNF,如下所示:
S → mXY | mY | mXC | mC | p
X → mX | m
Y → mXD | mD | o
O → o
P → p
廣告