Любое регулярное множество, которое распознается КА, можно описать с помощью автоматной грамматики. Алгоритм построения грамматики следующий:
1.Начальный символ грамматики - начальное состояние КА.
2.Терминальные символи грамматики - алфавит КА (без символа
"конец цепочки" --+).
3.Нетерминальные символы грамматики - множество состояний КА.
4.Если в таблице переходов КА есть переход из состояния А в состояние В при поступлении входного символа х - ввести правило следующего вида: А -> xB .
5.Если D - допускающее состояние КА, то ввести правило следующего вида: D -> @ (@-пустая цепочка).
Пример Задан КА a b -+
- входной алфавит V={a,b, -+}; = > A ¦ A B ¦ доп
- множество состояний S={A,B,C}; ¦ ¦
- начальное состояние A; B ¦ A C ¦ отв
- множество допускающих состояний ¦ ¦
S1={A,C}. C ¦ C B ¦ доп
L--------
Построить грамматику, языком которой будет множество цепочек, допускаемых заданным КА.
Решение
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 -> @ (7); C -> @(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 в G1 с укороченым множеством правил Р.
2.Если в множестве правил Р для одинаковых левых частей правые части правил начинаются с одинакового терминального символа, то при построении получится НКА-распознаватель, который затем можно
преобразовать в КА-распознаватель.
Пример
Для грамматики G[Z] построить КА-распознаватель.
G[Z] = (VT={a,b,c}; VN={ Z,A,B }; Z; P={Z->aA, A->bA, A->cB, B->cZ,
B->b, A->a}).
Решение
1.Проверка нетерминалов грамматики G[Z] на продуктивность и достижимость.
а) продуктивны нетерминалы A и В (на основании двух последних правил); на основании первого правила продуктивен нетерминал Z;
б) достижими все терминалы (правила 1 и 3).
2.Зададим параметры автомата-распознавателя:
- входной алфавит {a,b,c,-+};
- множество состояний автомата S={Z,A,B,F};
- начальное состояние автомата - Z;
- множество допускающих состояний автомата S1={ F };
- таблица переходов (управляющая таблица автомата) имеет вид:
г=======T=====T======T======T===T==¬
¦ ¦ a ¦ b ¦ c ¦ -+ ¦
¦-------+-----+------+------+------¦
¦ Z ¦ A ¦ E ¦ E ¦ отв. ¦
¦-------+-----+------+------+------¦
¦ A ¦ F ¦ A ¦ B ¦ отв. ¦
¦-------+-----+------+------+------¦
¦ B ¦ E ¦ F ¦ Z ¦ отв. ¦
¦-------+-----+------+------+------¦
¦ F ¦ E ¦ E ¦ E ¦ доп. ¦
L=======¦=====¦======¦======¦======-
По виду таблицы переходов видно (в каждой клетке одно состояние), что получен КА-распознаватель, который можно проверить
на эквивалентность состояний и минимизировать (проверить самостоятельно).
Проверка работы КА: Пусть задана цепочка из грамматики G[Z] abccaa (вывод в грамматике получить самостоятельно).
Необработанная Текущее состояние Новое состояние
цепочка КА - расп-ля КА - расп-ля
abccaa-+ Z A
bccaa-+ A A
ccaa-+ A B
caa-+ B Z
aa-+ Z A
a-+ A F
-+ F доп.
Примечание: по самому левому символу необработанной цепоки и текущему состоянию КА в соответствии с таблицей переходов вырабатывается новое состояние.
Заданная цепочка будет допущена построенным КА-распознавателем.