Введение к работе
Актуальность темы
В диссертационной работе рассматривается задача построения псевдооптимального регулярного выражения для заданного недетерминированного конечного автомата. Решение этой задачи вносит свой вклад в общую задачу звёздно-высотной минимизации недетерминированных конечных автоматов в частности, а также в решение проблемы звёздной высоты в целом.
Конечные автоматы и регулярные языки широко применяются во многих приложениях. Например, в лексическом и синтаксическом анализе, программах обработки текста, языках запросов и т. д. В некоторых приложениях важен способ представления конечных автоматов в памяти компьютера. В частности, актуальна минимизация автоматов по различным критериям. Такая минимизация позволяет увеличить эффективность работы конкретного программного приложения. В качестве одного из критериев минимизации конечных автоматов может выступать звёздная высота -максимальная вложенность операции «звезда Клини» (обозначение - *) в эквивалентном регулярном выражении.1
Рассматриваемая задача относится к классу труднорешаемых,2 и получение приемлемого решения даже для автоматов небольшой размерности, как правило, представляет собой сложную проблему.3 Поэтому актуальной является задача построения эвристических алгоритмов реального времени (т. н. anytime-алгоритмов4) - для поиска псевдооптимального регулярного выражения для регулярного языка, заданного с помощью недетерминированного конечного автомата. В каждый определённый момент работы таких алгоритмов можно получить лучшее (на данный момент) решение, а последовательность таких решений в пределе обычно даёт оптимальное решение.
В то же время рассматриваемая задача тесно связана с проблемой звёздной высоты, которая является фундаментальной проблемой в теории формальных языков.5 Для данной проблемы на сегодняшний день не найден алгоритм, приемлемый для программной реализации. Предлагаемые в
1 Саломаа А. Жемчужины теории формальных языков. М. : Мир, 1986. 159 с.
2 Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М. : Мир,
1982.416 с.
3 Lombardy S., Sakarovitch J. Star Height of Reversible Languages and Universal Automata II
5th Latin American Theoretical Informatics Symposium. LNCS, 2002. Vol. 2286.
4 Мельников Б. Мультиэвристический подход к задачам дискретной оптимизации // Ки
бернетика и системный анализ (НАН Украины). 2006. № 3. С. 32-42.
5 Kirsten D. Distance desert automata and the star height problem II Theoret. Informatics Appl.
2005. № 39. P. 455-509.
диссертационной работе алгоритмы могут быть полезны при разработке нового подхода к решению проблемы звёздной высоты.
Таким образом, решение поставленной задачи имеет как теоретическое, так и практическое значение.
В диссертационной работе также приводится описание обобщённых регулярных выражений и предлагается вариант модели обобщённого конечного автомата. Данные варианты конечных автоматов и регулярных выражений позволяют задавать такие описания регулярных языков, которые могут содержать дополнения регулярных множеств. В некоторых случаях (например, при контекстном поиске) описание языка в таком виде удобнее, чем описание языков с помощью классических конечных автоматов и регулярных выражений. Разработан алгоритм поиска обобщённого регулярного выражения для заданного обобщённого конечного автомата, в котором также могут быть применены алгоритмы звёздно-высотной минимизации.
Цель работы
Целью работы является разработка и реализация эвристических алгоритмов для решения задачи звёздно-высотной минимизации недетерминированных конечных автоматов (далее по тексту - «задача»).
Основные задачи исследования:
Исследование и реализация переборных методов решения рассматриваемой задачи, исследование их эффективности.
Разработка и реализация эвристик для определения порядка удаления состояний автомата в методе элиминации вершин, позволяющих получить приближённое решение.
Исследование и реализация методов усреднения количественных результатов работы эвристических алгоритмов, в частности применение динамических оценок состояний автомата.
Разработка и реализация anytime-алгоритма, позволяющего найти лучшее решение за указанный промежуток времени или точное решение.
Проведение вычислительных экспериментов и анализ работы разработанных алгоритмов.
Описание модели обобщённых конечных автоматов и обобщённых регулярных выражений, позволяющих определять дополнения регулярных языков. Разработка и реализация алгоритма построения обобщённого регулярного выражения для заданного обобщённого конечного автомата.
Объект исследования
Объектами исследования являются регулярные языки и формализмы для их описания - недетерминированные конечные автоматы и регулярные выражения.
Предмет исследования
Предметом исследования являются алгоритмы построения псевдооптимального регулярного выражения по недетерминированному конечному автомату.
Методы исследования
В качестве аппарата исследований применялись математические методы разработки и анализа алгоритмов, математическое и компьютерное моделирование.
Научная новизна
Научная новизна диссертационной работы заключается в разработке новых эвристических алгоритмов для решения задачи звёздно-высотной минимизации недетерминированных конечных автоматов. Данная задача возникает, например, при лексическом и синтаксическом анализе, в контекстном поиске и других приложениях, а её решение может улучшить эффективность работы этих приложений. В диссертационной работе впервые предложены такие алгоритмы решения данной задачи, которые приемлемы для программной реализации.
Разработаны эвристические алгоритмы, с помощью которых можно быстро (и при этом с достаточной точностью) получать приближённые решения задачи построения псевдооптимального регулярного выражения по заданному конечному автомату.
Показана возможность получения приемлемых вариантов реализации мультиэвристического подхода для создания anytime-алгоритмов решения рассматриваемой задачи, значительно более эффективных, чем переборные методы. С помощью anytime-алгоритма можно получить лучшее решение задачи, найденное за определённый пользователем промежуток времени, или точное решение, если время решения неограниченно.
Описана модель обобщённого конечного автомата и разработан алгоритм построения обобщённого регулярного выражения для заданного обобщённого конечного автомата. Такие варианты описания регулярных языков в некоторых приложениях значительно удобнее, чем их описание с помощью классических формализмов. Для предложенной модели также возможно применение представленных в работе алгоритмов уменьшения звёздной высоты.
Разработан программный комплекс, реализующий предложенные модели и алгоритмы.
Практическая значимость исследования
Предложенные в работе алгоритмы могут быть применены в различных прикладных задачах теории формальных языков (например, при описании языков программирования).
Разработанные алгоритмы и модели могут быть полезны в контекстном поиске по нескольким образцам или по регулярному выражению. В
этих задачах для осуществления поиска по заданным образцам строится недетерминированный конечный автомат, а его минимизация увеличивает скорость последующего поиска.
Данные алгоритмы также вносят свой вклад в поиск эффективных алгоритмов для решения проблемы звёздной высоты. Кроме того, предложенные подходы могут найти применение и в других предметных областях.
Достоверность результатов
Достоверность результатов подтверждается результатами экспериментов, сравнением результатов работы алгоритмов с применением разработанных эвристик и результатов решения задачи другими методами.
Основные положения, выносимые на защиту:
Описание эвристик для приближённого решения рассматриваемой задачи.
Методы усреднения нескольких эвристик. Применение динамических оценок состояний автомата и динамических функций риска.
Применение незавершённого метода ветвей и границ и вспомогательных эвристик для этого метода в рассматриваемой задаче. Описание соответствующего anytime-алгоритма.
Определение обобщённого конечного автомата и описание алгоритма построения эквивалентного ему обобщённого регулярного выражения.
Результаты вычислительных экспериментов, показывающие эффективность разработанных алгоритмов.
Апробация работы
Результаты диссертационной работы докладывались и обсуждались на:
XXIV международной научно-технической конференции «Математические методы и информационные технологии в экономике, социологии и образовании» (Пенза, декабрь 2009);
XXVI международной научно-технической конференции «Математические методы и информационные технологии в экономике, социологии и образовании» (Пенза, декабрь 2010);
VII международной научно-практической конференции «Динамика научных исследований - 2011» (Белгород, июль 2011);
4) тринадцатой международной научно-технической конференции
«Моделирование, идентификация, синтез систем управления - 2011» (пос.
Канака, Украина, сентябрь 2011);
5) международной научно-практической конференции «Молодёжь и нау
ка: модернизация и инновационное развитие страны» (Пенза, сентябрь 2011).
Публикации
По теме диссертации опубликовано 8 работ, из них 2 - в изданиях, рекомендованных ВАК.
Личный вклад автора
Постановка задач осуществлялась научным руководителем. Описываемые в диссертации эвристики и подходы, разработанные алгоритмы реше-
ния поставленных задач выполнены автором самостоятельно либо в соавторстве с научным руководителем. Эвристики для приближённого решения задачи, а также эвристики для ветвления и вычисления границ в незавершённом методе ветвей и границ разработаны автором самостоятельно.
Структура и объём диссертации
Диссертация состоит из введения, 10 глав, 1 приложения и списка литературы, состоящего из 87 наименований источников отечественных и зарубежных авторов. Общий объём диссертации составляет 123 страницы.
