原文 https://www.tutorialspoint.com/automata_theory/cfg_simplification.htm

在上下文無關(guān)文法（CFG）中，可能出現(xiàn)所有符號都不需要進(jìn)行推導(dǎo)的情況惨好。另外渡贾，文法中可能含有空產(chǎn)生式(null production)和單產(chǎn)生式(unit production)。消除這些產(chǎn)生式和符號，就叫 CFG化簡 商叹∧屡浚化簡本質(zhì)上包含以下步驟：

• CFG規(guī)約
• 去除單產(chǎn)生式
• 去除空產(chǎn)生式

規(guī)約文法

文法用兩個(gè)周期來規(guī)約

Phase 1 - 從文法 G 推導(dǎo)等價(jià)文法 G^' ， 每個(gè)變量導(dǎo)出一些終結(jié)符號窟却。（從開始符號開始推導(dǎo)）

推導(dǎo)過程
Step 1 - 包含所有符號 W₁昼丑，并初始化 i=1 。
Step 2 - 包含可以導(dǎo)出 W_i 的所有符號 W_i+1 夸赫。
Step 3 - 重復(fù) Step 2菩帝，直到 W_i+1 = W_i 。
Step 4 - 包含所有的含有 W_i 的產(chǎn)生式規(guī)則茬腿。

Phase 2 - 從文法 G' 推導(dǎo)等價(jià)文法 G''呼奢，對于每個(gè)出現(xiàn)在句法形式的符號。

推導(dǎo)過程
Step 1 - 包含所有符號 Y₁切平，并初始化 i=1 握础。
Step 2 - 包含可以從 Y_i 導(dǎo)出的所有符號 Y_i+1 ，并包含應(yīng)用的所有產(chǎn)生式悴品。
Step 3 - 增加 i 禀综， 重復(fù) Step 2 郎哭，直到 **Y_i+1 = Y_i 。

問題

找到一個(gè)規(guī)約后的等價(jià)文法G菇存，包含以下產(chǎn)生式： P:
小寫是終結(jié)符號夸研。

S -> AC | B
A -> a
C -> c | BC
E -> aA | e

解決

Phase 1

T = { a, c, e}
W₁ = { A, C, E} 從規(guī)則 A -> a，C -> c 和 E -> aA
W₂ = { A, C, E} U { S } 從規(guī)則 S -> AC
W₃ = { A, C, E, S } U ?
因?yàn)?W₃ = W₂依鸥，所以我們導(dǎo)出
G’ = { { A, C, E, S }, { a, c, e }, P, {S}}
也就是

S → AC
A → a
C → c 
E → aA | e

Phase 2

Y₁ = { S }
Y₂ = { S, A, C } 從規(guī)則 S → AC
Y₃ = { S, A, C, a, c } 從規(guī)則 A → a and C → c
Y₄ = { S, A, C, a, c }
因?yàn)閅₃ = Y₄亥至，所以我們推導(dǎo)出 G'' :
G” = { { A, C, S }, { a, c }, P, {S}}

S → AC
A → a
C → c

消除單產(chǎn)生式

任何產(chǎn)生式，具有 A -> B 的形式(A, B ∈ 非終結(jié)符) 就叫 單產(chǎn)生式 贱迟。

消除過程

Step 1 要消除 A -> B 姐扮，用 B -> x 的體添加到規(guī)則中 A -> x 。 [x ∈ 終結(jié)符衣吠， x 可以是 Null]
Step 2 從規(guī)則中刪除 A -> B 茶敏。
Step 3 重復(fù)步驟1直到所有的單產(chǎn)生式都被消除。

問題

從以下規(guī)則消除單產(chǎn)生式：

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

解決

文法中有三個(gè)單產(chǎn)生式：

Y → Z
Z → M
M → N

我們首先消除 M -> N 缚俏。

因?yàn)?N -> a 惊搏，我們添加 M -> a， 并且移去 N -> a忧换。

產(chǎn)生式變成了：

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

然后移去 Z -> M

因?yàn)?M -> a恬惯， 我們添加 Z -> a 并且移去 M -> a 。

現(xiàn)在變成了

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

現(xiàn)在我們移去 Y -> Z

因?yàn)?Z -> a亚茬， 我們添加 Y -> a 并且移去 Z -> a 酪耳。

現(xiàn)在變成

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

現(xiàn)在 Z， M刹缝， N 不可到達(dá)碗暗， 所以我們?nèi)サ羲?/p>

最后產(chǎn)生式變成

S → XY
X → a
Y → a | b

消除空產(chǎn)生式

文法中含有 A → ε， 或者從 A開始最后到達(dá)ε梢夯， A->...->ε言疗。

消除過程

Step 1 - 找到所有產(chǎn)生ε的非終結(jié)符。
Step 2 - 對于所有產(chǎn)生式 A -> α厨疙， 構(gòu)建所有產(chǎn)生式 A -> β洲守。β是從α去掉一個(gè)或者多個(gè) A（步驟一中的）。
Step 3 - 將原產(chǎn)生式與Step 2的結(jié)果合并沾凄，并去除掉空產(chǎn)生式梗醇。

問題

從以下去除空產(chǎn)生式：

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

解決

有兩個(gè)nullable， A 和 B 撒蟀。
我們首先消除 B -> ε

S -> ASA | aB | b | a
A -> B| b | ε
B -> b

現(xiàn)在消除 A -> ε

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