鏈接: https://www.tutorialspoint.com/automata_theory/chomsky_normal_form.htm

CFG(Chomsky Normal Form)，喬姆斯基規(guī)范形式， 具有以下形式：

A -> a
A -> BC
S -> ε

小寫字母表示終結(jié)符號(hào)，大寫表示非終結(jié)符。
產(chǎn)生式的體要么由單個(gè)終結(jié)符號(hào)或者ε構(gòu)成，要么由兩個(gè)非終結(jié)符構(gòu)成。

規(guī)范形式變換算法

Step 1 - 如果開(kāi)始符 S 出現(xiàn)在產(chǎn)生式的右側(cè) 創(chuàng)建一個(gè)新符號(hào)
S' -> S 。
Step 2 - 去除掉空產(chǎn)生式。
Step 3 - 去除掉單產(chǎn)生式。
Step 4 - 替換每個(gè)產(chǎn)生式 A -> B₁...B_n 對(duì) n > 2 變換成 A -> B₁C C -> B₂...B_n 。重復(fù)此過(guò)程，直到最后。
Step 5 - 產(chǎn)生式右側(cè)的終結(jié)符號(hào) A -> aB ， 替換為 A -> XB ， X -> a ， 重復(fù)此過(guò)程，直到替換掉全部終結(jié)符號(hào)。

問(wèn)題

轉(zhuǎn)換以下文法到規(guī)范形式：

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

解決

(1) 因?yàn)?S 出現(xiàn)在右側(cè) S -> ASA ，所以我們添加 S₀ ，S₀ -> S。

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

(2) 現(xiàn)在去除空產(chǎn)生式

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) 現(xiàn)在我們?nèi)コ龁萎a(chǎn)生式：

去掉 S → S：

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

去掉 S₀→ 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) 現(xiàn)在變換多于兩個(gè)變量的右側(cè)

這里 S₀→ ASA, S → ASA, A→ ASA 都是

變換后：

S0 → AX | aB | a | AS | SA
S → AX | aB | a | AS | SA
A → b |AX | aB | a | AS | SA
B → b
X → SA

(5) 我們最后將終結(jié)符組合產(chǎn)生式S₀→ 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