格雷巴赫正規化



如果產生式具有以下形式,則 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

廣告