去掉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