解释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+ 次浏览

开启你的职业生涯

通过完成课程获得认证

开始学习
广告