将 CFG 转换为 CNF
Convert a CFG into CNF
我还是 CFG and CNF 的新手，有时在理解这些概念时遇到困难。
我正在尝试将此 CFG 转换为乔姆斯基范式：
G: S -> aSbS | bSaS | epsilon
我认为该语言会生成所有具有相同数量的 a 和 b 的字符串，即 {a^n b^n |n>-0}。
但是要将其转换为 CNF，我已经完成了添加新的开始状态并消除了 epsilon-productions：
S_0 -> S | epsilon
S -> aSbS | bSaS | aS | bS | a | b
也许我需要两个非终端（变量）A -> a 和 B -> b :
S_0 -> S | epsilon
S -> ASBS | BSAS | AS | BS | a | b
A -> a
B -> b
我被困在这里，真的不知道下一步应该做什么。似乎没有单元制作或无用的符号。
乔姆斯基正态是通过具有以下形式的所有产生式来定义的：
A -> BC（其中 A、B 和 C 是任意非终结符）
A -> a（其中 A 是任意非终结符，a 是任意终结符）
或 S -> epsilon
除此之外，开始符号可能永远不会出现在任何产生式的右侧。
任何 CFG 到 CNF 的一般转换包括 4 个步骤（Wikipedia 使用术语 START、TERM、BIN、DEL、UNIT，所以让我们使用它们）
操作的顺序可能会有所不同，但这是常用的一般顺序。
START：消除出现在右侧的任何开始符号。
这是通过引入新的起始符号 S0 并添加产生式 S0 -> S.
来实现的
TERM：从右侧超过 1 个符号的产品中删除所有终端，这就是您要做的。
BIN：将所有右边减少到最多两个符号。这是通过引入新的非终结符来实现的，如下所示：
给定 A -> X1,...,Xn 我们通过引入新的非终结符并拆分右侧来简单地减少右侧以满足要求，如下所示：
A -> X1,..,Xn-2,A1
A1 -> Xn-1,Xn
重复此过程，直到右侧长度为 2 个符号。
DEL：从右侧消除 epsilon（当然 S -> epsilon 除外，如果 epsilon 是语言的一部分），您已经完成。
UNIT: 移除单元产生式 (A -> B)
这是通过用所有可能的产品代替单位产品的结果来实现的。例如
A -> B
B -> a | X1X2
将导致 B 在右侧被其产生式替换：
A -> a | X1X2
和 B 及其作品一起被删除。
通常这些步骤可以按任意顺序执行，但请注意，在许多情况下，后面步骤的效果可能会破坏前面步骤所满足的条件。
希望对您有所帮助。
最终输出：
S -> XY | YX | AS | BS | a | b
A -> a
B -> b
X ->AS
Y ->BS
我还是 CFG and CNF 的新手，有时在理解这些概念时遇到困难。
我正在尝试将此 CFG 转换为乔姆斯基范式：
G: S -> aSbS | bSaS | epsilon
我认为该语言会生成所有具有相同数量的 a 和 b 的字符串，即 {a^n b^n |n>-0}。
但是要将其转换为 CNF，我已经完成了添加新的开始状态并消除了 epsilon-productions：
S_0 -> S | epsilon
S -> aSbS | bSaS | aS | bS | a | b
也许我需要两个非终端（变量）A -> a 和 B -> b :
S_0 -> S | epsilon
S -> ASBS | BSAS | AS | BS | a | b
A -> a
B -> b
我被困在这里，真的不知道下一步应该做什么。似乎没有单元制作或无用的符号。
乔姆斯基正态是通过具有以下形式的所有产生式来定义的：
A -> BC（其中 A、B 和 C 是任意非终结符）
A -> a（其中 A 是任意非终结符，a 是任意终结符）
或 S -> epsilon
除此之外，开始符号可能永远不会出现在任何产生式的右侧。
任何 CFG 到 CNF 的一般转换包括 4 个步骤（Wikipedia 使用术语 START、TERM、BIN、DEL、UNIT，所以让我们使用它们）
操作的顺序可能会有所不同，但这是常用的一般顺序。
START：消除出现在右侧的任何开始符号。
这是通过引入新的起始符号 S0 并添加产生式 S0 -> S.
TERM：从右侧超过 1 个符号的产品中删除所有终端，这就是您要做的。
BIN：将所有右边减少到最多两个符号。这是通过引入新的非终结符来实现的，如下所示：
给定 A -> X1,...,Xn 我们通过引入新的非终结符并拆分右侧来简单地减少右侧以满足要求，如下所示：
A -> X1,..,Xn-2,A1
A1 -> Xn-1,Xn
重复此过程，直到右侧长度为 2 个符号。
DEL：从右侧消除 epsilon（当然 S -> epsilon 除外，如果 epsilon 是语言的一部分），您已经完成。
UNIT: 移除单元产生式 (A -> B) 这是通过用所有可能的产品代替单位产品的结果来实现的。例如
A -> B
B -> a | X1X2
将导致 B 在右侧被其产生式替换：
A -> a | X1X2
和 B 及其作品一起被删除。
通常这些步骤可以按任意顺序执行，但请注意，在许多情况下，后面步骤的效果可能会破坏前面步骤所满足的条件。
希望对您有所帮助。
最终输出：
S -> XY | YX | AS | BS | a | b
A -> a
B -> b
X ->AS
Y ->BS