将给定的上下文无关文法转换为 CNF
问题
将给定的语法转换为乔姆斯基范式(CNF)
S->AAA|B
A->aA|B
B->ε
解决方案
按照下面给出的步骤将CFG转换为CNF-
步骤1 -消除epsilon产生
要消除epsilon产生，必须在所有其他产生的RHS上替换产生epsilon的变量，以便移除epsilon产生。
在所有其他产生式中用ε替换B给出以下产生式集-
S->AAA|ε|乙
A->aA|ε|乙
在所有其他产生式中用\epsilon替换A给出以下结果-
S->AAA|AA|一个|乙|ε[分别用ε替换1、2和3个A]
A->aA||乙
由于文法产生字符串ε，因此无法消除剩余的ε-产生式以使文法保持等价。去除最后的ε-产生式得到一个与原始文法G有以下关系的文法G'-
L(G')=L(G)-{ε}
G'中的产品如下-
S->AAA|AA|一个|乙
A->aA||乙
步骤2 -消除单元生产
消除单元生产的过程如下-
选择一个生产A->B，使得存在非单位生产B->a
对于每个非单位生产，B->a重复以下步骤-
将产生式A->a添加到语法中。
从语法中消除A->B。
从语法中消除单元生产S->A，获得以下语法-
S->AAA|AA|一个||乙
A->aA||乙
B没有生产，因此不能消除类型V->B的单位生产。
第3步-无用的符号
B是一个无用的符号，因为它没有产生式。所以可以去掉。
A->a产生一个终端字符串，并且它可以从S到达，因此A不是无用的
类似地，S也不是无用的，因为可以从中产生端子。
所以去除无用符号后得到的CFG是-
S->AAA|AA|一个|一种
A->aA|一种
乔姆斯基范式(CNF)
要将语法转换为乔姆斯基范式，所有在右侧具有两个以上元素的产生式都需要通过添加更多变量将其拆分为两个或更多产生式。
右侧至少有两个符号的产生式中的终结符需要用变量符号替换。
添加以下生产以生产终端a-
Z->a
结果语法如下-
S->AAA|AA|赞|一种
A->ZA|一种
Z->一个
生产S->AAA通过添加附加变量T进行修改。
这给出了以下语法-
S->TA|AA|赞|一种
T->AA
A->ZA|一种
Z->一个
在上面的语法中，所有的产生式都是A->BC或A->b的形式。因此，它是乔姆斯基范式(CNF)。