Решение. Для каждого из двух нетерминалов в множестве правил Р имеется больше одного правила (предполагается

Для каждого из двух нетерминалов в множестве правил Р имеется больше одного правила (предполагается, что процедуры исключения непродуктивных и недостижимых нетерминалов уже выполнены).

1 Для нетерминала S:

" Выбор S(1)" = {a}; " Выбор S(2) " = {b}.

" Выбор S(1) " Ç " Выбор S(2) " = { } (пересечение пусто).

" Выбор S " = " Выбор S(1) " È " Выбор S(2) " = { a, b }.

2 Для нетерминала A:

" Выбор A(3) " = {c}; " Выбор A(4) " = " След A "

Определим отношение " След A ". После нетерминала A могут следовать "–|" (правило (1)) и " а ". В выводе:

1 3 1 (номера правил)

S à aA à acSa à acaAa à... (после нетерминала А появился терминал a).

Таким образом отношение " След A " = {–|, a}

" Выбор A(3) " Ç " Выбор A(4) " = {c} Ç {–|,a} = { } (пересечение пусто).

" Выбор A " = " Выбор A(3) " È " Выбор A(4) " = {c} È {–|,a} = {c,–|,a}.

Вывод: грамматика G[S] является q –грамматикой.

Для q –грамматики существует формальная процедура построения МП –распознавателя с одним состоянием по следующему алгоритму:

1 Входной алфавит МП –распознавателя V = {VT,–|}.

2 Множество магазинных символов { VN, VT1, #}, где VT1 – часть терминальных символов грамматики, которые встречаются в цепочках a множества правил.

3 Начальная конфигурация – в магазине находится начальный символ грамматики (например для грамматики G[S] – S #).

Примечание. Запись содержимого магазина ведем так, чтобы верхний символ (тот, с которым работает МП –автомат) занимал самую левую позицию.

4.Управляющая таблица строится так: столбцы таблицы – символы входного алфавита (последний символ –|); строки таблицы – магазинные символы. Заполнение управляющей таблицы:

а) для правил грамматики вида Х à y a (a – непустая цепочка терминалов и нетерминалов; y – терминал) клетка управляющей таблицы заполняется в соответствии с рис. а (см. на след.стр.);

б) для правил грамматики вида Х à y клетка управляющей таблицы заполняется в соответствии с рис. б (см. выше).

В соответствии с пп. а и б обрабатывается все множество Р правил грамматики (кроме эпсилон–правил);

в) заполнить клетки таблицы на пересечении терминал–магазинный символ и тот же терминал–входной алфавит в соответствии с рис в;

г) заполнить каждую клетку таблицы на пересечении нетерминала Z и входных символов МП –распознавателя из множества " След Z " в соответствии с рис. г;

д) все оставшиеся клетки последнего столбца таблицы (–|) заполняются " Отв. " кроме клетки на пересечении со строкой #, в которой ставится " Доп. ";

e) оставшиеся незаполненными клетки управляющей таблицы заполняются буквой Е (error) –"состояние ошибки".