Распознавание строк конечным автоматом

Определение Пара (q, t) Î Q´ T^*, где t - текущий остаток входной строки, называется конфигурацией автомата М.

Определение Конфигурация (q₀, t), где t - полная входная строка, называется начальной, а пара (q, e), где q Í Z, называется заключительной конфигурацией.

Шаг работы автомата можно представить отношением непосредственного следования конфигураций |-. Тогда, если F(q, t)=p, где pÎ Q, то можно записать (q, tt) |- (p, t) для всех t Î T^*. Эта запись означает то, что если автомат находится в состоянии q и входная головка обозревает входной символ t, то автомат может делать шаг, за который он переходит в состояние p и сдвигает головку на одну ячейку вправо.

Определение Автомат М допускает (принимает) строку t, если существует путь по конфигурациям (q, t) |- (q, e) для некоторого q Î Z.

Определение Язык L, принимаемый конечным автоматом М, формально определяется как множество:

L(M) = {t | t Î T^* и (q, t) |- (q, e) для некоторого q Î Z}.

Существуют следующие способы представления функции переходов:

- командный способ. Каждую команду КА записывают в форме , где .

- т абличный способ. Строки таблицы переходов соответствуют входным символам автомата t Î T, а столбцы – состояниям Q. Ячейки таблицы заполняются новыми состояниями, соответствующими значению функции . Неопределенным значениям функции переходов соответствуют пустые ячейки таблицы.

- графический способ.Строится диаграмма состояний автомата – неупорядоченный ориентированный помеченный граф. Вершины графа помечены именами состояний автомата. Дуга ведет из состояния в состояниe и помечается списком всех символов t Î T, для которых . Вершина, соответствующая входному состоянию автомата, снабжается стрелкой. Заключительное состояние на графе обозначается двумя концентрическими окружностями.

2.3.3 Преобразование конечных автоматов

Возникают две основных задачи эквивалентного преобразования КА:

1) преобразование недетерминированного конечного автомата в детерминированный конечный автомат;

2) минимизация КА.

2.3.3.1 Преобразование конечного автомата к детерминированному виду

В теории КА доказано, что для любого НКА существует ДКА, принимающий тот же регулярный язык. Рассмотрим этот алгоритм.

Алгоритм Преобразование НКА в ДКА

Вход: НКА .

Выход: ДКА .

Шаг 1. Пометить первый столбец таблицы переходов ДКА начальным состоянием (множеством начальных состояний) НКА .

Шаг 2. Заполняем очередной столбец таблицы переходов , помеченный символами , для этого определяем те состояния , которые могут быть достигнуты из каждого символа строки при каждом входном символе . Поместить каждое найденное множество (в том числе ) в соответствующие позиции столбца таблицы , т.е.:

для некоторого }

Шаг 3. Для каждого нового множества (кроме ), полученного в столбце таблицы переходов , добавить новый столбец в таблицу, помеченный .

Шаг 4. Если в таблице переходов КА есть столбец с незаполненными позициями, то перейти к шагу 2.

Шаг 5. Во множество ДКА включить каждое множество, помечающее столбец таблицы переходов и содержащее НКА .

Шаг 6. Составить таблицу новых обозначений множеств состояний и определить ДКА в этих обозначениях.

Этот алгоритм обеспечивает отсутствие недостижимых состояний ДКА, но не гарантирует его минимальности.

Пример Пример 2.1. Дана регулярная грамматика с правилами . Построить по регулярной грамматике КА и преобразовать полученный автомат к детерминированному виду.

Построим по НКА из примера 2.1 ДКА .

1 Строим таблицу переходов для ДКА (таблица 2.2).

Таблица 2.2 – Построение функции переходов для ДКА

Шаг
F	S	A, B	A, N	B, N	A	N	B
a	A, B	A, N	A	N	A		N
b		B, N	N	B	N		B

2 Во множество заключительных состояний автомата включим элементы .

3 Введем следующие новые обозначения состояний автомата : (A, B)=С, (A, N)=D, (B, N)=E.

4 Искомый ДКА определяется следующей пятеркой объектов: , , функция переходов задана таблицей 2.3, , .

Таблица 2.3 – Функция переходов для ДКА

	S	A	B	С	D	E	N
a	C	A	N	D	A	N
b		N	B	E	N	B

Граф полученного ДКА представлен на рисунке 2.1.

Рисунок 2.1 – Граф ДКА

⇐ Предыдущая 1 2 345 6 7 8 9 10 Следующая ⇒