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

 

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

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

Определим множество достижимых символов 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}. Множество недостижимых символов Тогда после удаления недостижимых символов, получим грамматику с правилом