Алгоритм Устранение нетерминалов, не порождающих терминальных строк

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

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

Шаг 1. Определить множество нетерминалов, порождающих терминальные строки, с помощью алгоритма 4.1.

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

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

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

N ₀ = Ø;

N ₁ = { S, B, C };

N ₂ = { S, B, C }.

Т.к. N ₁= N ₂, то N = { S, B, C }. После удаления бесполезных нетерминалов и правил вывода, получим грамматику с правилами