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

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

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

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

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

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

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

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

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

N0 = Ø;

N1 = {A, B};

N2 = {S, A, B};

N3 = {S, A, B}.

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






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