資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學消除 ε、單位和無用符號，並將文法改寫成 Chomsky 正規化 (CNF)
問題
消除給定文法的 ε、單位和無用符號，並將其改寫成 Chomsky 正規化 (CNF)。
S->0E0|1FF| ε
E->G
F->S|E
G->S| ε
解答
在給定的文法中，我們首先移除空產生式。文法中有兩個空產生式，如下所示：
S ==> ε
G ==> ε
因此，移除空產生式，並用 ε 重寫所有包含 G 的其他規則，同時保留舊的產生式。我們不移除 S ==> ε，因為它是一個開始符號。
移除 G ==> ε 後，我們得到：
S ==> 0E0 | 1FF | ε
E ==> G | ε
F ==> S | E
G ==> S
現在移除 E ==> ε，我們得到：
S ==> 0E0 | 1FF | 00 | ε
E ==> G
F ==> S | E | ε
G ==> S
現在移除 F ==> ε，我們得到：
S ==> 0E0 | 1FF | 00 | 1S | 1E | 1 | ε
E ==> G
F ==> S | E
G ==> S
現在，我們必須移除單位產生式，只有一個單位產生式 E ==> G 和 G ==> S，
透過移除 G ==> S，我們得到：
S ==> 0E0 | 1FF | 00 | 1S | 1E | 1 | ε
E ==> S
F ==> S | E
移除 E ==> S，我們得到：
S ==> 0S0 | 1FF | 00 | 1S | 1 | ε
F ==> S
移除 F ==> S，我們得到：
S ==> 0S0 | 1SS | 00 | 1S | 1 | ε
現在我們必須將其轉換為 Chomsky 正規化 (CNF)。因此，我們執行以下操作：
新增產生式 A ==> 0，B==>1，C ==> AS 和 D ==> BS，
我們得到最終文法如下：
S ==> CA | DS | BB | AS | 1 | ε
A ==> 0
B ==> 1
C ==> AS
D ==> BS
974 次瀏覽
