Решение. 1 Выполним проверку нетерминалов грамматики на достижимость и продуктивность: S достижим (начальный символ); R достижим (правило (1)); R продуктивен (правило

1 Выполним проверку нетерминалов грамматики на достижимость и продуктивность: S достижим (начальный символ); R достижим (правило (1)); R продуктивен (правило (3)); S продуктивен (правило (1)).

2 Построим МП –распознаватель (по виду правил делаем вывод, что это S –грамматика):

– входной алфавит V={a,b,–|};

– множество магазинных символов {S,R,b,#};

– начальное содержимое магазина S,#;

– управляющая таблица имеет вид (см. след.стр.);

3 Проверим работу МП –распознавателя.

Получим контрольную цепочку на основании правил грамматики:

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

S à bRbS à bRbabR à bRbabbR à bRbabba à bababba

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

Работу МП –распознавателя по разбору цепочки bababba представим в виде таблицы:

Необраб. цепочка	Обрабат. символ	Верхний символ магазина	Содержимое магазина	Действие с магазином
bababba–|	b	S	S#	Зам.RbS
ababba–|	a	R	RbS#	Выт.R
babba–|	b	b	bS#	Выт.b
abba–|	a	S	S#	Зам.bR
bba–|	b	b	bR#	Выт.b
ba–|	b	R	R#	Зам.R
a–|	a	R	R#	Выт.R
–|	–|	#	#	Допустить

Контрольная цепочка распознается построенным МП –распознавателем.

Работу МП–распознавателя можно трактовать так: на каждом шаге процесса обработки цепочки магазин представляет следующее утверждение о цепочке необработанных символов (включая текущий):

"вся цепочка будет допущена тогда и только тогда, когда оставшаяся необработанной цепочка входных символов выводима из цепочки символов, находящихся в магазине".

7.4 Построение МП–распознавателей для q – грамматик

КС –грамматика (2-й тип грамматики) называется q –грамматикой, если правые части всех правил этой грамматики начинаются с терминальных символов и для правил с одинаковыми левыми частями множества " Выбор " попарно не пересекаются.

Правила имеют вид Х à y a или Х à e, где y – терминал; a – любая цепочка терминалов и нетерминалов, возможно пустая; e – пустая цепочка (q -грамматика обязательно содержит хотя бы одно эпсилон–правило).

Примечание. q –грамматика отличается от S –грамматики только наличием в множестве Р эпсилон–правил; этот факт существенно усложняет построение МП –распознавателя.

Дадим определение ряду унарных отношений, которые можно построить на множестве { VT, –|}.

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

Отношение " Выбор Y " – подмножество множества входных символов МП –распознавателя, c которых могут начинаться цепочки, выводимые из нетерминала Y в любых сентенциальных формах, получаемых из множества Р правил грамматики.

Отношение " Выбор Y " в конкретной грамматике строится как объединение таких отношений, построенных для всех правил, содержащих в левых частях нетерминал Y. Если в левых частях множества правил Р нетерминал встречаетсятолько один раз, то строить отношение " Выбор " для него не нужно.

Для правил вида Y à x a (1) или Y à z (2) множество

" Выбор Y(n) " (n – номер правила в множестве Р) всегда равно первому терминалу правой части правила:

для правила (1) " Выбор Y(1) " = {x};

для правила (2) " Выбор Y(2) " = {z}.

Если в множестве Р правил грамматики нет больше правил для нетерминала Y, то отношение

" Выбор Y " = " Выбор Y(1) " È " Выбор Y(2) "; " Выбор Y " = {x,z}.

Для правила вида Y à e (3) отношение

" Выбор Y(3) " = " СледY " и определять его нужно, анализируя все множество Р правил грамматики (в примере будет подробно рассмотрена построение этого отношения).

Для q -грамматики условие "попарное пересечение множеств " Выбор " для правил с одинаковыми левыми частями должно быть пусто" гарантирует однозначность работы МП –распознавателя (правило грамматики применяется всякий раз, когда верхний магазинный символ является его левой частью, а входной символ принадлежит множеству " Выбор " этого правила).

Рассмотрим на примере процедуру проверки КС –грамматики на предмет ее принадлежности к классу q –грамматик.

Пример: Задана грамматика G[S] (VT = {a,b,c}; VN = {S,A}; S; P); P = {S à aA(1); S à b(2); A à cSa(3);

A à e (4)}.

Проверить принадлежность этой грамматики к классу q –грамматик.