theory - 将 CFG 转换为 CNF

Question

我对 CFG 和 CNF 还很陌生，有时难以理解这些概念。

我正在尝试将此 CFG 转换为乔姆斯基范式:

G: S -> aSbS | bSaS | epsilon

我认为该语言生成具有相同数量的 a 和 b 的所有字符串，即 {a^n b^n |n>-0}。

但是为了将其转换为 CNF，我已经添加了新的开始状态并消除了 epsilon-products:

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

我被困在这里，真的不知道下一步应该做什么。似乎没有单位产生式或无用的符号。

Answer 1

乔姆斯基范态的定义是具有以下形式的所有产生式:
A -> BC (其中 A、B 和 C 是任意非终结符)
A -> a (其中 A 是任意非终结符和任意终结符)
或S -> epsilon
除此之外，开始符号永远不会出现在任何产生式的右侧。

任何 CFG 到 CNF 的一般转换都包含 4 个步骤(Wikipedia 使用术语 START、TERM、BIN、DEL、UNIT，所以我们使用这些术语)

操作的顺序可能有所不同，但这是常用的一般顺序。

开始:消除出现在右侧的任何开始符号。 这是通过引入新的起始符号 S0 并添加产生式 S0 -> S 来实现的。

术语:从右侧具有超过 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 及其产品被删除。

通常，这些步骤可以按任意顺序完成，但请注意，在许多情况下，后面步骤的效果可能会破坏前面步骤满足的条件。

希望这有帮助。