context-free-grammar - 从上下文无关语法中删除空产生式

Question

X -> zZ|yW|WW
Y->Z
Z->X|ε
W->Y|X

我认为当 Y 只有 Z 作为它的终端时，ε 移动到 Y 给出：

X -> zZ|yW|WW
Y->Z|ε
Z->X
W->Y|X

然后？

X -> zZ|yW|WW|z
Y->Z
Z->X
W->Y|X

Answer 1

您错过了 w 产生式中 ε 从 Y 的传播。

X -> zZ|yW|WW|z
Y->Z
Z->X
W->Y|X|ε

然后向上移动：

X -> zZ|yW|WW|z|y|ε
Y->Z
Z->X
W->Y|X

并继续：

X -> zZ|yW|WW|z|y
Y->Z
Z->X|ε
W->Y|X|ε

我们回来了，我们开始了！没有 ε，这个文法就永远写不出来。

（除非有人想纠正我？）