构造指定上下文无关文法的CNF：无用符号判定及转换咨询

一、无用符号的判定逻辑 #

无用符号的核心判定标准：要么无法从起始符号S推导得到（不可达），要么无法推导出终结符串（不可终止）。先明确原文法：

原文法产生式：
S→aAa | bBb | ε
A→C|a
B→C|b
C→CDE | ε
D→A|B|ab
E（无对应产生式）

逐个分析符号：

• E：没有任何产生式定义，既无法被其他符号推导生成，自身也不能推导出终结符，属于完全无用的符号，必须直接删除。
• C、D：
  • 可达性：从S出发，通过S→aAa→aCa或S→bBb→bCb可推导到C；再通过C→CDE（删除E后变为C→CD）可推导到D，二者均可达。
  • 可终止性：D可通过D→a/D→b/D→ab直接生成终结符串；C可通过C→ε或C→CD→D（利用C的空产生式）推导到D，进而生成终结符串。因此C、D是有用符号，不能删除。

删除E后的精简文法：

S→aAa | bBb | ε
A→C|a
B→C|b
C→CD | ε
D→A|B|ab

二、转换为乔姆斯基范式（CNF）的步骤 #

CNF要求所有产生式满足以下两种形式之一：X→YZ（X、Y、Z为非终结符），或X→a（a为终结符）；仅允许起始符号保留S→ε（若存在）。

步骤1：消除ε产生式 #

先找出可空非终结符（能推导出ε的符号）：C、A、B、S。对每个产生式补充可空符号的替代情况：

• S：保留S→ε，添加S→aa（替代S→aAa中A为空的情况）、S→bb（替代S→bBb中B为空的情况），原S→aAa、S→bBb保留。
• A：保留A→a，添加A→ε（替代A→C中C为空的情况），原A→C保留。
• B：保留B→b，添加B→ε（替代B→C中C为空的情况），原B→C保留。
• C：保留C→ε，添加C→D（替代C→CD中C为空的情况），原C→CD保留。
• D：保留D→ab，添加D→ε（替代D→A/D→B中A/B为空的情况），原D→A、D→B保留。

去重后得到消除ε的文法：

S→aAa | aa | bBb | bb | ε
A→C | a | ε
B→C | b | ε
C→CD | D | ε
D→A | B | ab | ε

步骤2：消除单产生式（X→Y，X、Y为非终结符） #

将所有单产生式替换为目标符号能直接推导的非单产生式：

• 把A→C替换为A→CD、A→D（保留原A→a、A→ε）
• 把B→C替换为B→CD、B→D（保留原B→b、B→ε）
• 把C→D替换为C→A、C→B、C→ab（保留原C→CD、C→ε）
• 把D→A替换为D→C、D→a（保留原D→B、D→ab、D→ε）
• 把D→B替换为D→C、D→b（去重后保留原D→C、新增D→b）

消除单产生式后的文法：

S→aAa | aa | bBb | bb | ε
A→CD | D | a | ε
B→CD | D | b | ε
C→CD | A | B | ab | ε
D→C | a | b | ab | ε

步骤3：处理长产生式与终结符组合 #

• 引入新非终结符X→a、Y→b，将终结符组合替换为非终结符组合：
  • D→ab替换为D→XY
  • S→aa替换为S→XX，S→bb替换为S→YY
• 拆分右部长度为3的产生式S→aAa、S→bBb：
  • 引入S1→AX，则S→XS1
  • 引入S2→BY，则S→YS2

步骤4：标准化起始符号（可选） #

若要求严格CNF中起始符号S不出现于其他产生式右部，可引入新起始符号S'，添加S'→S | ε，保留原S的所有产生式。

最终的CNF文法示例：

S'→S | ε
S→XS1 | YS2 | XX | YY
S1→AX
S2→BY
A→CD | D | X | ε
B→CD | D | Y | ε
C→CD | A | B | XY | ε
D→C | X | Y | XY | ε
X→a
Y→b

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