1.3.3.Построение конечных детерминированных автоматов для распознавания регулярных языков

Из теории формальных языков известно, что конечные детерминированные автоматы способны распознавать регулярные языки []. В связи с этим актуальна задача построения автомата, распознающего по множеству примеров некий язык. Для решения этой задачи успешно применялись различные генетические алгоритмы. Задача может быть усилена до построения автомата с минимальным количеством состояний. Однако, в работе [] показано, что эта задача является NP-трудной. В работе [] автоматы представлялись с помощью таблицы переходов. Разработанный в этой работе метод позволяет поддерживать в популяции автоматы с разным числом состояний. Функция приспособленности учитывает три компонента – количество верно распознанных тестовых примеров, количество состояний и переходов автомата, степень общности языка, соответствующего построенному автомату. Это позволяет сузить область поиска, и находить языки, соответствующие определенным критериям. В тестовую коллекцию могут входить примеры слов, которые как принадлежат, так и не принадлежат языку. Приведем описание генетической операции репродукции. Число состояний потомка выбирается случайно из диапазона [N – 2, N + 2], где N — число состояний первого родителя. После этого каждый переход копируется из родителей, причем вероятность копирования перехода из заданной особи прямо пропорциональна значению ее функции приспособленности. Переходы, представленные только в одном из родителей, копируются из того родителя, в котором присутствуют. Переходы, отсутствующие в обоих родителях, генерируются случайно.  Генетическая операция мутации осуществляется изменением случайного перехода. При этом переход разрешается удалять. Это приводит к распаду графа переходов на несколько компонент. Результаты экспериментов показали, что удаление недостижимых состояний замедляет вывод – поэтому оно не производится. Предложенный подход был проверен на практических задачах. Авторам удалось построить автомат из семи состояний, который распознает по множеству из ста примеров русские двухсложные слова. В работе [] для генерации автомата был применен следующий вариант генетического программирования: выводилось выражение, результатом вычисления которого являлся автомат. Выражение описывало последовательность действий, преобразующих исходный автомат () в результирующий. Для вывода выражений, кодирующих развитие автомата, было применено традиционное генетическое программирование, оперирующее над деревьями выражений.

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

• PARALLEL – создать новое допускающее состояние автомата и направить туда активную дугу. При этом созданное состояние копируется из состояния, в которое активная дуга вела до операции;

• PARALLEL-REJ – создать новое отвергающее состояние и направить туда активную дугу аналогично PARALLEL;

• RETRACT – зациклить активную дугу: направить ее в состояние, из которого она исходит;

• WRITE-NODE – положить в стек состояние, в которое ведет активная дуга;

• TO-NODE – снять состояние со стека и направить в него активную дугу. Если стек пуст, то активная дуга не модифицируется.

В работе [] введен единственный терминал DONE, означающий конец редактирования. Пример выражения, использующего эти функции, приведен на . Для наглядности нетерминалы пронумерованы в порядке исполнения. Для нетерминалов PARALLEL и PARALLEL-REJ первый аргумент соответствует действиям, совершаемым над созданным состоянием. При этом активная дуга переходит в первую дугу, исходящую из нового состояния. Второй аргумент этих нетерминалов соответствует действиям, совершаемым над исходным состоянием. При этом активная дуга заменяется следующей дугой, исходящей из состояния. Для остальных нетерминалов единственный аргумент вычисляется аналогично второму аргументу PARALLEL и PARALLEL-REJ.

На показан процесс развития автомата из исходного по приведенному выражению.

Известно, что регулярные языки могут быть представлены как объединение, пересечение или дополнение других регулярных языков. Следовательно, можно произвести декомпозицию языка на более простые языки, для которых проще найти распознающие автоматы. В работе [] определено решение в виде комбинации трех автоматов через нетерминалы AND, OR и NOT. Разложение также определяется с помощью генетического программирования. Пример выведенного с помощью этой методики распознавателя изображен на .

Описанный подход был протестирован на наборе из девяти регулярных языков. К сожалению, для одного из тестовых языков так и не удалось построить автоматический распознаватель.  В работе [] произведено сравнение двух подходов к автоматическому построению автоматов: использование генетических алгоритмов и применение эвристики Evidence Driven State Merging (EDSM). После анализа проведенных экспериментов был сделан вывод, что автомат, построенный с помощью генетических алгоритмов, лучше соответствует искомому языку. С другой стороны, эвристика EDSM всегда строит автомат, который верно распознает множество примеров.  Кроме этого, в работе [] предлагается подход, позволяющий существенно сократить пространство поиска в задаче построения конечного автомата для распознавания регулярного языка. Этот подход состоит в том, что в хромосоме генетического алгоритма кодируется только структура автомата, а его вершины помечаются одним из значений – «допускающее состояние» или «не допускающее состояние» – с помощью процедуры, которую авторы работы назвали «расстановкой пометок» (smart state labeling). Применение этого подхода позволило существенно ускорить работу генетического алгоритма. ^