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

 

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

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 доп.

 

Примечание: по самому левому символу необработанной цепоки и текущему состоянию КА в соответствии с таблицей переходов вырабатывается новое состояние.

Заданная цепочка будет допущена построенным КА-распознавателем.