Алгоритм Устранение недостижимых символов

Вход: КС-грамматика .

Выход: КС-грамматика , такая, что и для всех существует вывод , где .

Определим множество достижимых символов Z грамматики G, т.е. множество

Шаг 1. Положить

Шаг 2. Вычислить очередное приближение следующим образом:

Шаг 3. Если то положить i:= i +1 и перейти к шагу 2, иначе считать .

Шаг 4. Вычислить , где - это множество правил, содержащих недостижимые символы .

Пример Данаграмматика с правилами

Преобразуем ее в эквивалентную грамматику по алгоритму 4.3:

W ₀ = { S };

W ₁ = { S, a, b };

W ₂ = { S, a, b }.

Т.к. W ₁= W ₂, то W ={ S, a, b }. Множество недостижимых символов Тогда после удаления недостижимых символов, получим грамматику с правилом