Решение. 1 Проверка нетерминалов на продуктивность

1 Проверка нетерминалов на продуктивность.

В правых частях правил (5) и (6) только терминалы. Внесем в создаваемый список продуктивных нетерминалы B и, D. Затем в соответствии с правилом (3) – A (в правой части терминал и продуктивный нетерминал); в соответствии с правилом (2) – S; анализ других правил список не пополняет. Получен исчерпывающий список продуктивных нетерминалов – { B, D, A, S}. В списке отсутствует нетерминал С (непродуктивный, правило (4) для минимизации исходной грамматики исключим из множества P).

2 Проверка нетерминалов на достижимость.

Внесем на первом шаге в создаваемый список достижимых нетерминалов начальный символ грамматики S, затем на основании правила (2) дополним список нетерминалом A; правило(3) дает основания внести в список нетерминал В. Дальнейший анализ правил в соответствии с алгоритмом поиска достижимых нетерминалов список не пополняет. Получен исчерпывающий список продуктивных нетерминалов – {S,A,B}. В списке отсутствует нетерминал D (недостижимый, правило (6) для минимизации исходной грамматики исключим из множества P).

В результате этих преобразований получили минимальную грамматику G1[S], эквивалентную исходной.

G1[S]: VN = {S, A, B}; VT = {a, b, d}; начальный символ S;

P = { S à aS (1), S à aA (2), A à bB (3), B à d (4) }.

Добавление нетерминала

Не нарушая эквивалентности часть цепочки, составляющей правую часть любого правила исходной грамматики, можно обозначить новым нетерминалом (добавить нетерминал в множество VN) и дополнить множество правил P правилом, определяющим новый нетерминал.

Пример: Пусть в исходной грамматике G одно из правил имеет вид A à abВc. Обозначив bB через новый нетерминал N, заменим это правило двумя: A à aNc; N à bB.

Не нарушая эквивалентности процедуру добавления нетерминала можно применять многократно.

Подстановка правил

В множество правил P исходной грамматики, не нарушая эквивалентности, можно добавить новые правила, которые получаются в результате подстановки в любое правило, содержащее в правой части нетерминалы, их значений из других правил. При этом правила, участвовавшие в подстановках, можно исключить из множества Р.

Другими словами, в множество Р можно добавить правило

A à х, если A⁺à х (т.е. цепочка х выводима из А в исходной грамматике).