将给定的语法转换为乔姆斯基范式 (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 | 一种
要将语法转换为乔姆斯基范式，所有在右侧具有两个以上元素的产生式都需要通过添加更多变量将其拆分为两个或更多产生式。
右侧至少有两个符号的产生式中的终结符需要用变量符号替换。
添加以下生产以生产终端 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)。