2014-12-12 5 views

ответ

0

Вы пропустили распространение ε из 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|ε 

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

(Если кто-то не хочет меня исправлять?)