Эквивалентный CFG (контекстно-свободная грамматика) без нулевого производства - PullRequest
0 голосов
/ 13 мая 2019

Для грамматики, приведенной ниже, каков эквивалент CFG без нулевых продукций?

S->ASB/epsilon
A->Aa/epsilon
B->bB/epsilon.

1 Ответ

0 голосов
/ 15 мая 2019

Правило таково: если 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, поскольку входная грамматика генерирует пустую строку.

...