CFG转CNF转换中起始符号为非生成符号的处理方法咨询

先看你给出的CFG：

S -> ASB
A -> aA | a
B -> b

首先明确：生成非终结符是能推导出纯终结符字符串的非终结符，反之则是非生成的。你说S是非生成的完全正确——S的唯一产生式右侧包含自身，无论怎么推导，结果里永远会保留S，根本无法得到全由终结符组成的串。

移除非生成非终结符的具体步骤 #

1. 标记所有生成非终结符

   • B可直接推导出终结符b，属于生成非终结符。
   • A既能直接推导出a，也能通过aA递归最终得到a，同样是生成非终结符。
   • S无法推导出纯终结符串，标记为非生成。

2. 清理相关产生式
   所有涉及非生成非终结符的产生式都要移除，这里就是S -> ASB这条。清理后剩下的有效产生式为：

   A -> aA | a
   B -> b
   

3. 处理起始符号的特殊情况
   原起始符号S是非生成的，这意味着原CFG实际上不生成任何语言（因为起始符号无法推导出终结符串）。移除非生成符号后剩下的产生式对应的语言是a的正闭包加上单独的b，但这和原CFG的空语言是完全不同的两个概念。

为什么有些网站没移除这类非生成非终结符 #

不少工具的优化逻辑不够严谨：比如只移除“既非生成又不可达”的非终结符，但S是起始符号，属于可达的非生成非终结符，部分工具会跳过移除；还有些工具仅执行了移除无用符号的部分步骤，没有严格遵循移除非生成符号的完整规范，最终导致结果不符合要求。

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