去掉epsilon、unit和无用符号，改写成CNF
问题
消除给定语法的 epsilon、unit 和无用符号，并将其重写为 CNF。
S->0E0|1FF| ε
E->G
F->S|E
G->S| ε
解决方案
在给定的语法中，我们将首先删除空产生式。语法中有两个空产生式，如下所示 -
S ==> ε
G ==> ε
因此，删除空产生式并通过 epsilon 重写所有其他包含 G 的规则以及旧产生式。我们不会删除 S ==> epsilon，因为它是开始符号。
删除 G ==> epsilon，我们得到以下结果 -
S ==> 0E0 | 1FF | ε
E ==> G | ε
F ==> S | 乙
G ==> S
现在删除 E ==> epsilon，我们得到以下结果 -
S ==> 0E0 | 1FF | 00 | ε
E ==> G
F ==> S | E | ε
G ==> S
现在删除 F ==> epsilon，我们得到以下结果 -
S ==> 0E0 | 1FF | 00 | 1S | 1E | 1 | ε
E ==> G
F ==> S | 乙
G ==> S
现在，我们必须去除单位生产，只有一个单位生产 E ==> G 和 G ==> S，
通过删除 G ==> S，我们得到以下结果 -
S ==> 0E0 | 1FF | 00 | 1S | 1E | 1 | ε
E ==> S
F ==> S | 乙
删除 E ==> S，我们得到以下结果 -
S ==> 0S0 | 1FF | 00 | 1S | 1 | ε
F ==> S
删除 F ==> S，我们得到以下结果 -
S ==> 0S0 | 1SS | 00 | 1S | 1 | ε
现在我们必须将其转换为乔姆斯基范式 (CNF)。因此，我们执行以下操作 -
添加产生式 A ==> 0, B==>1, C ==> AS 和 D ==> BS,
我们得到最终的语法如下 -
S ==> CA | DS | BB | AS | 1 | ε
一个 ==> 0
B ==> 1
C ==> AS
D ==> BS
以上是 去掉epsilon、unit和无用符号，改写成CNF 的全部内容， 来源链接： utcz.com/z/349133.html
