double arrow

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

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

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

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

Шаг 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 }, следовательно, язык грамматики существует, потому что начальный символ .


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: