Удаление нулевых произведений из контекстно-свободной грамматики

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

Вы пропустили распространение ε от Y в производстве w.

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|ε

и мы вернулись, мы начали! Эта грамматика никогда не может быть написана без ε.

(Разве кто-то хочет меня поправить?)