Вход: КС-грамматика .
Выход: заключение о существовании или отсутствии языка грамматики.
Определим множество нетерминалов, порождающих терминальные строки .
Шаг 1. Положить N 0=Ø.
Шаг 2. Вычислить и
Шаг 3. Если , то положить i = i +1 и перейти к пункту 2, иначе считать .
Если , то выдать сообщение о том, что язык грамматики существует, иначе сообщить об отсутствии языка.
Пример Дана грамматика , где множество правил : . Построим последовательность приближений множества N:
N 0 = Ø;
N 1 = { A, B };
N 2 = { S, A, B };
N 3 = { S, A, B }.
Т.к. N 2= N 3, то N = { S, A, B }, следовательно, язык грамматики существует, потому что начальный символ .