如何将给定文法转换为乔姆斯基范式(Chomsky Normal Form,CNF)？

转换严格遵循CNF的标准流程执行，原文法如下：

S → ASA | aB
A → B | S
B → b | ε

步骤1：消去ε产生式 #

首先确定可空非终结符集合：{A, B}（B可直接推出ε，A可通过B间接推出ε，S无法推出ε）。
对所有含可空非终结符的产生式，生成省略可空符号的所有合法非空右部，删除所有X→ε形式的产生式，无意义的循环产生式S→S直接删除，得到文法：

S → ASA | AS | SA | aB | a
A → B | S
B → b

步骤2：消去单产生式（右部仅含单个非终结符的产生式） #

当前单产生式为A→B、A→S，将其替换为对应非终结符的所有非单产生式右部，删除原单产生式，得到文法：

S → ASA | AS | SA | aB | a
A → ASA | AS | SA | aB | a | b
B → b

步骤3：拆分长度大于2的产生式右部 #

当前仅S→ASA、A→ASA右部长度为3，引入新非终结符C，新增规则C→AS，将原长度为3的产生式拆分：

S → CA | AS | SA | aB | a
A → CA | AS | SA | aB | a | b
B → b
C → AS

步骤4：替换混合右部中的终结符 #

当前S→aB、A→aB右部同时包含终结符和非终结符，不符合CNF要求，引入新非终结符D，新增规则D→a，将右部的终结符a替换为D，最终得到合法的CNF文法：

S → CA | AS | SA | DB | a
A → CA | AS | SA | DB | a | b
B → b
C → AS
D → a

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