Рассмотрим ряд преобразований, позволяющих "улучшить" вид контекстно-свободной грамматики без изменения порождаемого ею языка.
Назовем символ
Назовем символ
Очевидно, что каждый недостижимый и/или несводимый символ является бесполезным, как и все правила, его содержащие.
При внимательном изучении вышеприведенных определений становится понятным, что а) целесообразно искать не непосредственно сами недостижимые (или несводимые) символы, а последовательно определять множество достижимых (или сводимых) символов, начиная с тех, которые по определению являются достижимыми (аксиома) и сводимыми (терминалы) - все остальные символы оказываются бесполезными, б) одновременное определение достижимых и сводимых символов невозможно, так как соответствующие процессы идут в противоположных направлениях (от корня к листьям и наоборот).
Алгоритм 4.1. Устранение недостижимых символов.
Вход. КС-грамматика G = (N, T, P, S).
Выход. КС-грамматика G' = (N', T', P', S) без недостижимых символов, такая, что L(G') = L(G).
Метод. Выполнить шаги 1-4:
(1) Положить V0 = {S} и i = 1,
(2) Положить Vi = {X | в P есть A
(3) Если Vi
(4) Положить N' = Vi
Алгоритм 4.2. Устранение несводимых символов.
Вход. КС-грамматика G = (N, T, P, S).
Выход. КС-грамматика G' = (N', T', P', S) без несводимых символов, такая, что L(G') = L(G).
Метод. Выполнить шаги 1-4:
(1) Положить N' = T и i = 1,
(2) Положить
(3) Если Ni