資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究解釋在上下文無關文法中去除單元產生式
並非所有文法都經過最佳化，這意味著文法可能包含一些額外的符號（非終結符），從而增加了文法的長度。
因此，我們必須透過去除無用符號來簡化文法。
屬性
下面解釋了簡化文法的屬性：
- G 的每個非終結符和終結符都出現在 L 中某個單詞的推導中。
- 不應該有任何形如 X->Y 的產生式，其中 X 和 Y 都是非終結符。
- 如果語言 L 中不包含空串 ε，則在產生式 X-> ε 中也不需要包含 ε。
下圖描述了簡化文法的屬性：
單元產生式是指一個非終結符推匯出另一個非終結符的產生式。
去除單元產生式
下面給出去除單元產生式的步驟：
- 步驟 1 - 為了去除 X->Y，每當 Y->a 出現在文法中時，將產生式 X->a 新增到文法規則中。
- 步驟 2 - 現在從文法中刪除 X->Y。
- 步驟 3 - 重複步驟 1 和 2，直到所有單元產生式都被去除。
示例
考慮下面給出的上下文無關文法，併為其去除單元產生式。
S->0A|1B|C
A->0S|00
B->1|A
C->01
解釋
步驟 1
S->C 是單元產生式，但在去除 S->C 時，我們必須考慮 C 推匯出什麼，以便我們可以向 S 新增一個規則。
S->0A|1B|01
步驟 2
B->A 也是單元產生式
B->1|0S|00
最後，我們可以將不含單元產生式的 CFG 寫成如下形式：
S->0A|1B|01
A->0S|00
B->1|0S|00
C->01
更新於：2021年6月16日
17K+ 次瀏覽
廣告