解释在上下文无关文法中去除单元产生式

并非所有文法都经过优化，这意味着文法可能包含一些额外的符号（非终结符），从而增加了文法的长度。

因此，我们必须通过去除无用符号来简化文法。

属性

下面解释了简化文法的属性：

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

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告