Решение. 1 Выполним проверку нетерминалов грамматики G[Z] на продуктивность и достижимость

1 Выполним проверку нетерминалов грамматики G[Z] на продуктивность и достижимость.

а) продуктивны нетерминалы A и В (на основании правил (5) и (6)); на основании правила (1) продуктивен нетерминал Z (все терминалы продуктивны);

б) достижимы все терминалы (правила (1) и (3)).

2 Зададим параметры КА –распознавателя:

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

– множество состояний автомата S={Z,A,B,F};

– начальное состояние автомата – Z;

– множество допускающих состояний автомата S1={ F };

– таблица переходов (управляющая таблица) КА –распознавателя имеет вид:

Анализируя таблицу переходов (в каждой клетке одно состояние) делаем вывод, что получен КА –распознаватель, состояния которого можно проверить на эквивалентность, достижимость и,при необходимости, минимизировать (выполнить самостоятельно).

Проверка работы построенного КА– распознавателя. Пусть задана цепочка из языка грамматики G[Z]: abccaa (вывод получить самостоятельно).

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

Необработанная цепочка	Текущее состояние КА–распознавателя	Новое состояние КА–распознавателя
abccaa –| bccaa –| ccaa –| caa –| aa –| a --| --|	Z A A B Z A F	A A B Z A F Допустить

7.2 Построение КА–распознавателей для праволинейных грамматик

Праволинейной называется такая контекстно–свободная грамматика(КС –грамматика), в правых частях правил которой имеется не более одного нетерминала и этот нетерминал заканчивает правило.

Примечание. В множестве правил праволинейных грамматик допускаются эпсилон–правила (правила вида X à e т.е. нетерминал преобразуется в пустую цепочку).

Праволинейную грамматику всегда можно преобразовать в автоматную, для которой построение КА –распознавателя рассмотрено в предыдущем разделе. Алгоритм преобразования правил следующий:

а) преобразовать правила вида A à xyzB, где xyz – цепочка терминалов произвольной длины (в данном случае | xyz | = 3); вводят дополнительные нетерминалы по следующему принципу:

A à x<yzB>; <yzB> à y<zB>; <zB> à zB (в угловых скобках записаны цепочки, для обозначения которых вводят новые нетерминалы). Таким образом происходит замена исходного правила несколькими, которые соответствуют правилам автоматной грамматики. В нашем случае:

A à xM

A à xyzB M à yN

N à zB

б) преобразовать правила вида A à xyz, где xyz – цепочка терминалов произвольной длины (в данном случае | xyz | = 3); вводится дополнительный нетерминал F, который в КА –распознавателе будет служить финишным состоянием (подробнее см. разд. 7.1), а в преобразованной грамматике добавляется правило F à e.

A à xyzF (преобразование см. п. а)

A à xyz

F à e

В результате таких преобразований получим автоматную грамматику, эквивалентную исходной праволинейной. Как строить для автоматной грамматики КА –распознаватель описано в разделе 7.1.

Примечания:

1 При построении таблицы переходов в последнем столбце ставить " Доп. " для всех состояний КА –распознавателя, для которых в полученной грамматике есть эпсилон-правила.

2 Полученный КА –распознаватель обязательно проверить на достижимость и эквивалентность состояний; при необходимости выполнить процедуру преобразования в минимальный КА (переименование состояний не изменит множества распознаваемых цепочек).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример: Задана грамматика G[S] = (VT = {a,b};

VN = {S,R}; S; P), где P = { S à abR (1);S à bRbS (2);R à a (3);

R à bR (4) }.

Построить МП –распознаватель для языка, порождаемого этой грамматикой.