Правило таково: если X -> epsilon, то вы можете добавлять произведения в форме Y -> rs везде, где есть производство, такое как Y -> rXs, а затем исключать X -> epsilon.Единственное исключение состоит в том, что производство S -> epsilon не может быть удалено без удаления пустой строки из сгенерированного языка.Если некоторые нетерминалы оказываются эквивалентными, они должны быть сведены к одному символу, чтобы избежать петель.
S -> 0X0 | 1Y1 |€
X -> Z | 0
Y -> ZYU | €
Z -> 0Z1 | XZWZ | €
W -> X | Y | 01
Мы можем начать с Y:
S -> 0X0 | 1Y1 | 11 | epsilon
X -> Z | 0
Y -> ZYU | ZU
Z -> 0Z1 | XZWZ | epsilon
W -> X | Y | 01 | epsilon
Давайте к W следующим:
S -> 0X0 | 1Y1 | 11 | epsilon
X -> Z | 0
Y -> ZYU | ZU
Z -> 0Z1 | XZWZ | XZZ | epsilon
W -> X | Y | 01
Давайте сделаем Z следующим:
S -> 0X0 | 1Y1 | 11 | epsilon
X -> Z | 0 | epsilon
Y -> ZYU | ZU | YU | U
Z -> 0Z1 | XZWZ | XZZ | 01 | XWZ | XZW | XW | XZ | X
W -> X | Y | 01
Видим произведения X -> Z и Z -> X;поэтому эти символы эквивалентны.Объединение:
S -> 0X0 | 1Y1 | 11 | epsilon
X -> 0 | epsilon | 0X1 | 01 | XW | XX
Y -> XYU | XU | YU | U
W -> X | Y | 01
Теперь давайте сделаем X:
S -> 0X0 | 1Y1 | 11 | 00 | epsilon
X -> 0 | 0X1 | 01 | W | XX
Y -> XYU | XU | YU | U
W -> X | Y | 01 | epsilon
Мы видим произведения X -> W и W -> X;поэтому эти символы эквивалентны.Объединение:
S -> 0X0 | 1Y1 | 11 | 00 | epsilon
X -> 0 | 0X1 | 01 | XX | Y | epsilon
Y -> XYU | XU | YU | U
Мы снова делаем X:
S -> 0X0 | 1Y1 | 11 | 00 | epsilon
X -> 0 | 0X1 | 01 | XX | Y
Y -> XYU | XU | YU | U
Это должно сделать это, если только одно из правил, которые я использовал, было неверным (эквивалентные символы могут быть объединены, правило для исключенияepsilon), одно из упрощений, которое я сделал, было ошибочным, или я ошибочно предположил (что U - терминал, поскольку он не находится на LHS производства).