将CFG转换为CNF时，如何消除D→bD|D的单元产生式？

针对给定的上下文无关文法，我们按以下步骤处理，重点解决D→bD|D中的单元产生式问题：

1. 先处理ε产生式（消除空产生式） #

原文法中B→ε是空产生式，会影响其他规则的推导，先处理它：

• 对包含B的规则，补充B推导出ε后的等价规则：
  • S→DBC | Ba 补充为 S→DBC | Ba | DC | Da（当B→ε时，DBC变为DC，Ba变为Da）
  • C→aCb | aC | Bb 补充为 C→aCb | aC | Bb | ab（当B→ε时，Bb变为ab）
• 删除B→ε，此时B的规则为B→0B1 | 01

2. 消除单元产生式 #

单元产生式指形如A→B（A、B为非终结符，包括自循环A→A）的规则：

• 针对D→bD|D：其中D→D是自循环的单元产生式，它不会产生任何新的推导结果，直接删除这条规则即可。处理后D的规则简化为D→bD
• 检查其他非终结符（S、B、C）的规则，当前无其他单元产生式，无需额外处理

3. 转换为乔姆斯基范式（CNF） #

CNF要求所有规则只能是非终结符→两个非终结符或非终结符→单个终结符，因此需要拆分规则并引入辅助非终结符：

步骤3.1 引入对应单个终结符的辅助非终结符 #

定义：

• T_0→0
• T_1→1
• T_a→a
• T_b→b

步骤3.2 改写所有规则以符合CNF要求 #

• S的规则：
  • S→DBC 拆分为 S→D X1 和 X1→B C（X1为新辅助非终结符）
  • S→Ba 改写为 S→B T_a
  • S→DC 保留（已符合二元非终结符规则）
  • S→Da 改写为 S→D T_a
• D的规则：
  • D→bD 改写为 D→T_b D
• B的规则：
  • B→0B1 拆分为 B→T_0 X2 和 X2→B T_1（X2为新辅助非终结符）
  • B→01 改写为 B→T_0 T_1
• C的规则：
  • C→aCb 拆分为 C→T_a X3 和 X3→C T_b（X3为新辅助非终结符）
  • C→aC 改写为 C→T_a C
  • C→Bb 改写为 C→B T_b
  • C→ab 改写为 C→T_a T_b

最终的乔姆斯基范式文法 #

S → D X1 | B T_a | D C | D T_a
X1 → B C
X2 → B T_1
X3 → C T_b
D → T_b D
B → T_0 X2 | T_0 T_1
C → T_a X3 | T_a C | B T_b | T_a T_b
T_0 → 0
T_1 → 1
T_a → a
T_b → b

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