转换为乔姆斯基范式时，能否简化单元产生式S→Z？

原上下文无关文法 #

S -> wZx | WyX | Z | yX | Wy | y 
W -> wW | w
X -> xX | x 
Z -> zZ | z

你的修改尝试（错误原因分析） #

你将S→Z替换为Z的产生式，得到：

S -> wZx | WyX | zZ | z| yX | Wy | y 
W -> wW | w
X -> xX | x 

这个修改错误的核心是：它只完成了单元产生式消除的第一步，但不符合乔姆斯基范式的最终要求。乔姆斯基范式严格规定所有产生式只能是以下两种形式之一：

• 非终结符 → 两个非终结符（如A→BC）
• 非终结符 → 单个终结符（如A→a）

你的修改中S→zZ这种产生式（终结符+非终结符）违反了范式要求，所以不是正确的最终结果。

正确处理方式 #

单元产生式S→Z绝对不能保留原样，乔姆斯基范式要求必须消除所有单元产生式（除非是允许起始符号推导出空串的特殊情况，这里不涉及）。完整的处理步骤分为两步：

1. 消除单元产生式

对于单元产生式S→Z，将Z的所有非单元产生式（Z→zZ | z）添加到S的产生式中，同时移除S→Z。此时得到中间文法：

S -> wZx | WyX | zZ | z | yX | Wy | y
W -> wW | w
X -> xX | x 
Z -> zZ | z

2. 转换为乔姆斯基范式要求的形式

引入新的非终结符来表示单个终结符，再拆分所有不符合范式的产生式：

• 新增非终结符：

  W0 -> w
  X0 -> x
  Y0 -> y
  Z0 -> z
  

• 替换复合产生式：
  • S→wZx → S→W0 Z1，新增Z1→Z X0
  • S→WyX → S→W Y1，新增Y1→Y0 X
  • S→zZ → S→Z0 Z
  • S→yX → S→Y0 X
  • S→Wy → S→W Y0
• 替换单个终结符产生式：
  • S→z → S→Z0
  • S→y → S→Y0
• 调整原有非终结符的产生式：
  • W→wW → W→W0 W，W→w → W→W0
  • X→xX → X→X0 X，X→x → X→X0
  • Z→zZ → Z→Z0 Z，Z→z → Z→Z0

最终符合乔姆斯基范式的文法为：

S -> W0 Z1 | W Y1 | Z0 Z | Z0 | Y0 X | W Y0 | Y0
W -> W0 W | W0
X -> X0 X | X0
Z -> Z0 Z | Z0
W0 -> w
X0 -> x
Y0 -> y
Z0 -> z
Z1 -> Z X0
Y1 -> Y0 X

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