CFG转CNF时先移除useless productions再移除unit productions有何问题

直接给结论：把无用产生式移除步骤提前到单位产生式移除之前，要么会得到带冗余的非最简CNF文法，要么在实现不严谨时直接生成和原文法不等价的错误结果，完全不建议这么做。

核心问题有两个：

• 单位产生式移除操作本身会生成新的无用符号与无用产生式
  移除单位产生式的核心逻辑是：对任意一对满足「A可以通过若干条连续单位产生式到达B」的非终结符对(A,B)，把B的所有非单位产生式复制一份给A，最后删除所有单位产生式。这个过程会让单位产生式链上的中间非终结符彻底失去被引用的场景，变成新的无用符号。
  举个最直观的例子，以下是已经完成空产生式移除的初始文法：

  S → A | x
  A → B | y
  B → z
  

  如果先执行无用产生式移除：此时S、A、B三个非终结符都满足「可达+可推导出终结符」的要求，会被全部保留，没有产生式被删除。
  接下来执行单位产生式移除：
  1. 先求出所有单位对：(S,A)、(S,B)、(A,B)
  2. 给S补B的非单位产生式S→z、A的非单位产生式S→y
  3. 给A补B的非单位产生式A→z
  4. 删除所有原单位产生式S→A、A→B
     最终得到的产生式集合为：

  S → x | y | z
  A → y | z
  B → z
  

  此时A和B从来没有出现在任何产生式的右侧，属于完全冗余的无用符号，对应的产生式也是无效的。但因为你提前做完了无用产生式删除，没有在所有产生式修改操作完成后再清理，这些冗余就会全部留在最终结果里。这类带冗余的文法虽然表面上产生式格式符合CNF要求，但会给后续CYK解析等依赖CNF的算法引入完全不必要的时间、空间开销，也不符合CNF转换的最简要求。
• 提前执行无用产生式移除，很容易因逻辑不严谨出现误判，导致文法不等价
  无用产生式的判定需要两轮不动点迭代：先迭代求出所有能推导出终结符串的可生成非终结符，再从开始符号出发迭代求出所有可达的非终结符，两类集合的交集才是需要保留的有效非终结符。如果你的判定逻辑没有做充分的迭代（比如只扫描一轮产生式就判定是否有用），在存在长单位产生式链的场景下，很容易把链路上层的有效非终结符误判为无用删除，直接导致最终文法描述的语言和原文法不一致。
  比如对文法S→A, A→B, B→b，如果做可生成判定时只迭代一轮，只会识别出B是可生成的，把S、A误删，最终得到的文法只能生成空串，和原文法生成的语言{b}完全不等价。

本质上CNF转换的顺序设计逻辑非常直白：所有会新增、修改产生式的操作（移除空产生式、移除单位产生式）都要先做完，最后再统一做一次全局的无用产生式清理，才能保证结果既等价又无冗余。就像你拆完所有快递再扫地，才不会留一地包装垃圾，中途扫一次地最后肯定留脏东西。

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