上下文无关文法(CFG)转乔姆斯基范式(CNF)的结果正确性核验

原上下文无关文法 #

S -> AB | a | ε
A -> a | C | Ca | ε
B -> C
C -> Ca | Cb | D
D -> Ca | a

你给出的转换结果 #

S -> AB | a | ε | CX | CY
A -> a | CY | CX
B -> a | CY | CX
C -> a | CY | CX
X -> a
Y -> b

校验结论 #

你的转换结果完全符合乔姆斯基范式的要求，是正确的，核对逻辑如下：

• 符合CNF核心规则：除起始符S可保留ε产生式外，其余所有产生式右部要么是单个终结符，要么是两个非终结符，且起始符S未出现在任何产生式的右部。
• 转换步骤符合规范：
  1. 消去ε产生式：仅S作为起始符保留ε规则，删除非起始符A的ε产生式，同时补充S→B的衍生规则（对应A推导为ε时，S→AB等价于S→B）
  2. 消去单产生式：将A->C、B->C、C->D这类右部仅单个非终结符的规则，通过替换非终结符的对应产生式全部消去，合并后得到A、B、C的产生式均为a、CX、CY
  3. 拆分长右部产生式：将长度大于2的Ca、Cb分别拆为CX、CY，新增X->a、Y->b规则匹配终结符要求
  4. 冗余规则清理：原非终结符D的规则已全部合并到C中，无需保留，最终规则无冗余、无遗漏，可覆盖原文法的所有生成串，不会生成原文法不支持的串。

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