CFG转换为CNF时的变量识别与产生式化简相关疑问

问题解答 #

1. ABa的组成判定 #

你对ABa的结构判断完全正确：它的右部由2个非终结符（变量A、B）+1个终结符a组成，总长度为3，确实属于需要拆分的长产生式。

2. 你的化简方案存在的问题 #

你的拆分思路是对的，但有两处不符合乔姆斯基范式（CNF）的规范：

• CNF要求产生式右部只能是两种形式：要么是单个终结符，要么是两个非终结符。你拆分后得到的S'->Xa、B->Yb这类「非终结符+终结符」的二元产生式不符合要求，需要把其中的单独终结符替换为对应映射的非终结符。
• 你遗漏了B->AbA的拆分，这个产生式右部长度为3，同样需要处理，且你设置的Y->AA和该产生式没有对应关系，属于错误拆分。

3. 正确的化简结果 #

这一步需要先给所有出现在多符号右部中的终结符设置专属映射变量，再拆分所有长度≥3的右部，最终结果如下：

// 终结符映射变量
Ca -> a
Cb -> b
// 原产生式替换后的拆分结果
S' -> CaA | XCa
S -> CaA | XCa
A -> AA | a
B -> YA | CbCb
// 长产生式拆分出来的新变量
X -> AB
Y -> ACb

补充说明 #

后续你还需要检查是否有不可到达的无用变量，移除后就完成了整个CNF的转换。

内容的提问来源于stack exchange，提问作者anonymous