Правило таково: если X: = epsilon, мы можем изменить любую продукцию Y: = rXs на Y: = rXs |RS и устранить производство X: = эпсилон.Давайте посмотрим, как это работает в вашем случае.Во-первых, мы можем к S.
S -> ASB | epsilon … becomes … S -> ASB | AB
A -> Aa | epsilon
B -> bB | epsilon
Теперь мы делаем A:
S -> ASB | AB … becomes … S -> ASB | SB | AB | B
A -> Aa | epsilon … becomes … A -> Aa | a
B -> bB | epsilon
Теперь мы делаем B:
S -> ASB | SB | AB | B … becomes … S -> ASB | AS | SB | AB | A | B | epsilon
A -> Aa | a
B -> bB | b
Мы не можем избавитьсяиз S -> epsilon, поскольку входная грамматика генерирует пустую строку.