Решение. 1 Начальный символ грамматики A

1 Начальный символ грамматики A.

2 Множество терминальных символов грамматики VT={a,b}.

3 Множество нетерминальных символов VN={A,B,C}.

4 Множество правил P ={ A à aA (1), A à bB (2),

B à aA (3), B à bC (4), C à aC (5), C à bB (6); A à e (7); C à e (8) }.

Для проверки правильности построения грамматики получим вывод цепочки aaabb, которая допускается заданным КА.

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

A à aA à aaA à aaaA à aaabB à aaabbC à aaabb.

Для всякой автоматной грамматики (3-й тип грамматики) можно построить КА –распознаватель. Алгоритм построения КА –распознавателя следующий:

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

2 Множество состояний S = {VN,F} (F -финишное состояние – единственное допускающее состояние КА –распознавателя).

3 Начальное состояние КА –распознавателя – начальный символ грамматики.

4 Множество допускающих состояний S1 = { F }.

5 Таблица переходов (управляющая таблица) строится следующим образом:

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

– обозначить строки таблицы символами состояниями (первая строка – начальное состояние КА –распознавателя);

– в соответствии с правилом X à yZ заполнить клетку таблицы на пересечении строки Х и столбца y переходом в состояние Z;

– в соответствии с правилом Х à z заполнить клетку таблицы на пересечении строки Х и столбца z переходом в состояние F;

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

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

Примечания:

1.Перед началом построения КА –распознавателя проверить множество нетерминалов грамматики G на продуктивность и достижимость; при необходимости выполнить эквивалентные преобразования грамматики G с целью ее упрощения.

2.Если среди множества правил Р в группах с одинаковыми левыми частями есть хотя бы два правила, правые части которых начинаются с одинакового терминального символа, то при построении по приведенному выше алгоритму получится НКА –распознаватель, который затем можно легко преобразовать в КА –распознаватель.

Пример: Для грамматики G[Z] построить КА –распознаватель. G[Z] = (VT={a,b,c}; VN={ Z,A,B }; Z; P={ Z à aA (1),

A à bA (2), A à cB (3), B à cZ (4), B à b (5), A à a (6)}).