Может ли существовать контекстно-свободная грамматика, где все ее символы бесполезны?

Question

Пусть G - не зависящая от контекста грамматика, определенная терминалами (a, b), начинающимися в S и имеющими переменные (A, B, C, D, E, F, G)

с этими правилами производства:

S -> aA | BD
A -> aA | aAB | aD
B -> aB | aC | BF
C -> Bb | aAC | E
D -> bD | bC | b
E -> aB | bC
F -> aF | aG | a
G -> a | b

Я попытался сначала уменьшить количество не генерирующих символов, удалив A, B, C и E. Затем, после отслеживания недоступных символов, я был исключен с S -> ничего.

Я успешно справился с десятками приложений, но это первый случай, когда моя грамматика саморазвивается.

Как это возможно? Что-то не так я сделал? Существуют ли какие-либо CFG только с бесполезными символами?

РЕДАКТИРОВАТЬ: я напоминаю шаги алгоритма:
1) удалить не генерирующие символы (генерирующий X имеет по крайней мере один производный X -> w, где w является строкой терминалов)
2) удалить недостижимые символы (X достижим, если S -> αXβ)

Answer 1

Для определения контекстно-свободной грамматики не требуется, чтобы ее символы были достижимыми или продуктивными , хотя каждая контекстно-свободная грамматика может быть преобразована в слабо строго эквивалентно (спасибо, rici ) грамматика без лишних символов. Однако, поскольку язык вашей грамматики не пуст, вы, вероятно, применили преобразования неправильно. Например, ваша грамматика генерирует строку aab:

S ⇒ aA  (S → aA)
  ⇒ aaD (A → aD)
  ⇒ aab (D → b)