解釋CFG中消除ε產生式

並非所有文法都是最優的，這意味著文法可能包含一些額外的符號（非終結符），從而增加文法的長度。

因此，我們必須透過去除無用符號來簡化文法。

屬性

簡化文法的屬性如下：

  • G的每個非終結符和終結符都出現在L中某個單詞的推導中。
  • 不應該有任何形如X→Y的產生式，其中X和Y是非終結符。
  • 如果ε不在語言L中，則產生式X→ε也不需要。

下圖描述了簡化文法的應用：

形如S→ε的產生式稱為ε產生式。

這些型別的產生式只能從不生成ε的文法中刪除。

步驟1

首先找到所有可以推匯出ε的可空非終結符。

步驟2

對於每個產生式A→a，構造所有產生式A。其中X是從'a'中刪除一個或多個步驟1中的非終結符得到的。

步驟3

現在將步驟2的結果與原始產生式合併，並刪除ε產生式。

示例

S→XYX

X→0X|ε

Y→1Y|ε

解釋

刪除ε產生式時，我們刪除規則X→ε和Y→ε。

為了保留CFG的含義，我們在X和Y出現的地方的右側放置ε。

S→XYX

如果右側的第一個X是ε

S→YX

類似地，如果右側的最後一個X是ε

S→XY

如果Y=ε，

S→XX

如果Y和X都是ε，

S→ε

如果兩個x都被替換了，

S→Y

現在S→XY|YX|XX|X|Y

現在讓我們考慮一下：

X→0X|ε

如果我們在右側為X替換ε，則：

X→0X|0

類似地，Y→1Y|1

刪除ε產生式後的CFG如下：

S→XY|YX|XX|X|Y

X→0X|0

Y→1Y|1

更新於：2021年6月16日

8K+ 次瀏覽

開啟你的職業生涯

透過完成課程獲得認證

開始學習
廣告