Преобразования НКА

Детерминированный конечный автомат

Детерминированный конечный автомат является специальным случаем недетерминированного конечного автомата, в котором

· отсутствуют состояния, имеющие λ-переходы;

· для каждого состояния s и входного символа а существует не более одной дуги, выходящей из s и помеченной как а.

Детерминированный конечный автомат имеет для любого входного символа не более одного перехода из каждого состояния. Если для представления функции переходов ДКА используется таблица, то каждая запись в ней представляет собой единственное состояние. Следовательно, очень просто проверить, допускает ли данный ДКА некоторую строку, поскольку имеется не более одного пути от стартового состояния, помеченный этой строкой. Следующий алгоритм имитирует поведение ДКА при обработке входной строки.

На рис. 13 показан граф переходов детерминированного конечного автомата, допускающего тот же язык (a|b)*abb, что и НКА на рис. 12. При работе с этим ДКА и входной строкой ababb алгоритм пройдет последовательность состояний 0, 1, 2, 1, 2, 3 и ответит «да».

Рис. 13. ДКА, допускающий строку (a|b)*abb

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

Например, НКА на рис. 12 имеет два перехода из состояния 0 для входного символа а – в состояние 0 или 1. Ситуации, в которых функция переходов многозначна, делают моделирование НКА с помощью компьютерной программы весьма сложной задачей. Определение допустимости утвер­ждает только, что должен существовать некоторый путь, помеченный входной строкой и ведущий от начального кзаключительному. Однако когда имеется много пу­тей для одной и той же входной строки, возможно, придется рассматривать их все, чтобы найти путь к заключительному состоянию или выяснить, что такого пути не существует.

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

В таблице переходов НКА каждая запись представляет собой множество состояний; в таблице переходов ДКА — единственное состояние. Общая идея преобразования НКА в ДКА состоит в том, что каждое состояние ДКА соответствует множеству состояний НКА. ДКА использует свои состояния для отслеживания всех возможных состояний, в которых НКА может находиться после чтения очередного входного символа. Таким образом, после чтения входного потока ДКА находится в состоянии, которое представляет подмножество состояний НКА, достижимых из стартового состояния HКА по пути, помеченному как . Количество состояний ДКА может оказаться экспоненциально зависящим от количества состояний НКА.

На рис. 14 показан еще один НКА, допускающий язык (a|b)*abb. Этот автомат получен с использованием алгоритма построения НКА по регулярному выражению.

Рис. 14. НКА для (a|b)*abb

Преобразование НКА в ДКА путем построения подмножеств дает пять различных множеств состояний:

А = {0, 1, 2, 4, 7} D = {1, 2, 4, 5, 6, 7, 9}

В = {1, 2, 3, 4, 6, 7, 8} Е = {1, 2, 4, 5, 6, 7, 10}

С = {1, 2, 4, 5, 6, 7}

Состояние А является начальным, а E — единственным заключительным состоянием. Полностью таблица переходов показана на рис. 15.

Состояние	Входной символ
a	b
А	В	C
В	В	D
С	В	С
D	В	Е
Е	В	С

Рис. 15. Таблица переходов для ДКА

Рис. 16. Результат применения построения подмножества к рис. 15.

Граф переходов, полученного в результате преобразований ДКА показан на рис. 16. Следует заме­тить, что ДКА на рис. 13 также допускает язык (а | b) *abb и имеет на одно состояние меньше.

Далее необходимо минимизировать количество состояний ДКА.

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

Изначально разбиение состоит из двух групп: заключительные состояния и незаключительные. Основной шаг состоит в том, чтобы взять некоторую группу символов скажем А = и входной символ а и посмотреть, какие переходы имеют состояния для этого входного символа. Если эти переходы представляют переходы в состояния, попадающие в две или более различных групп текущего разбиения, группу А разбиваем на подгруппы так, чтобы для каждого из подмножества переходы ограничивались одной группой текущего разбиения.

Процесс разбиения повторяется до тех пор, пока не останется групп, которые следует разбить. Таблица переходов детерминированного конечного автомата с минимальным числом состояний представлена на рис.17.

Состояние	Входной символ
a	b
А	В	А
В	В	D
D	В	Е
Е	В	А

Рис. 17. Таблица переходов оптимизированного автомата

Дата добавления: 2014-12-27