Алгоритм Проверка существования языка грамматики

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

Выход: заключение о существовании или отсутствии языка грамматики.

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

Шаг 1. Положить N ₀=Ø.

Шаг 2. Вычислить и

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

Если , то выдать сообщение о том, что язык грамматики существует, иначе сообщить об отсутствии языка.

Пример Дана грамматика , где множество правил : . Построим последовательность приближений множества N:

N ₀ = Ø;

N ₁ = { A, B };

N ₂ = { S, A, B };

N ₃ = { S, A, B }.

Т.к. N ₂= N ₃, то N = { S, A, B }, следовательно, язык грамматики существует, потому что начальный символ .