Преобразования КС-грамматик
Рассмотрим ряд преобразований, позволяющих «улучшить» вид контекстно-свободной грамматики, без изменения порождаемого ею языка.
Назовем символ X


грамматики. Иными словами, символ X является недостижимым, если в G не существует вывода S







Алгоритм 4.1. Устранение недостижимых символов.
Вход. КС-грамматика G = (N, T, P, S).
Выход. КС-грамматика G' = (N', T', P', S) без недостижимых символов, такая, что L(G') = L(G).
Метод. Выполнить шаги 1-4:








Назовем символ X




Алгоритм 4.2. Устранение бесполезных символов.
Вход. КС-грамматика G = (N, T, P, S).
Выход. КС-грамматика G' = (N', T', P', S) без бесполезных символов, такая, что L(G') = L(G).
Метод. Выполнить шаги 1-5:
- Положить N0 = и i = 1.
- Положить Ni = {A|A P и(Ni-1T)*}Ni-1.
- Если NiNi-1, положить i = i+1 и перейти к шагу 2. В противном случае положить Ne = Ni и перейти к шагу 4.
- Положить G1 = ((NNe){S}, T, P1, S), где P1 состоит из правил множества P, содержащих только символы из NeT.
- Применив к G1 алгоритм 4.1, получить G' = (N', T', P', S).
КС-грамматика без бесполезных символов называется приведенной. Легко видеть, что для любой КС-грамматики существует эквивалентная приведенная. В дальнейшем будем предполагать, что все рассматривамые
грамматики - приведенные.