Введение к работе
Актуальность темы. Ещё примерно с начала 1970-х годов в научных публикациях нередко стало прослеживаться мнение, что в теории регулярных языков и конечных автоматов уже решены практически все возможные задачи. Но впоследствии, с началом применения данной теории к различным вопросам из смежных наук, стало ясно, что для многих задач важен не только сам исследуемый регулярный язык, но и способ, которым он задаётся. Поэтому важными стали казаться вопросы исследования недетерминированных конечных автоматов, в том числе - вопросы их экономного представления в памяти компьютера. При разных способах представления автомата в памяти компьютера более важными могут быть либо минимально возможное число вершин, либо минимально возможное число дуг, либо некоторые другие критерии. Именно подобные проблемы и связаны с рассматриваемыми в диссертации алгоритмами.
Целью работы является разработка и описание алгоритмов эквивалентного преобразования недетерминированных конечных автоматов, разработка и описание математических моделей, дающих возможность успешного применения подобных алгоритмов в прикладных задачах дискретной оптимизации.
Основные задачи исследования:
Разработка и описание новых алгоритмов эквивалентного преобразования недетерминированных конечных автоматов.
Формулировка и доказательство теорем о корректности этих алгоритмов и свойствах отношения ф.
Разработка и описание математических моделей поиска в пространствах состояний, дающих возможность успешного применения разработанных алгоритмов в прикладных задачах дискретной оптимизации.
Объект исследования. Объектом исследования являются недетерминированные конечные автоматы Рабина-Скотта (Медведева).
Предмет исследования. Предметом исследования являются алгоритмы работы с недетерминированными конечными автоматами.
Методы исследования. В качестве аппарата исследований применяются методы доказательства теорем дискретной математики и методы разработки алгоритмов.
Результаты исследования. Результатами диссертационного
исследования являются новые утверждения, теоремы теории формальных языков, а также новые вычислительные алгоритмы и математические модели.
Научная новизна. Доказанные утверждения и теоремы, описанные алгоритмы эквивалентного преобразования недетерминированных конечных автоматов, разработанные модели поиска в пространстве состояний на множествах объектов, связанных с недетерминированными конечными автоматами, являются оригинальными разработками автора диссертации. Некоторые утверждения доказаны совместно с научным руководителем.
Практическая значимость исследования. Полученные
результаты могут быть применены в различных задачах минимизации недетерминированных конечных автоматов - в вершинной, дуговой и «звёздно-высотной» минимизации, а также минимизации по некоторым комбинированным критериям. При этом результаты могут быть применены и для создания эвристических алгоритмов решения перечисленных задач дискретной оптимизации.
Достоверность результатов. Достоверность результатов
подтверждается приведёнными в диссертации доказательствами утверждений и теорем.
Основные положения, выносимые на защиту.
Разработка новых алгоритмов эквивалентного преобразования недетерминированных конечных автоматов.
Доказательство теоремы о том, что, применяя операции объединения и дублирования, можно получить любой конечный автомат из заданного конечного автомата с одной компонентой связности через базисный конечный автомат.
Доказательство теоремы о том, что для двух конечных автоматов возможна любая таблица отношения #, в которой нет одинаковых, пустых строк и столбцов, а также если в «меньшем» из двух канонических автоматов имеется N состояний, то в «большем» из них - их не более, чем 2N — I.1
Разработка математической модели, которая представляет собой графоподобную структуру на множестве всех эквивалентных автоматов. Доказательство, что эта модель содержит все конечные автоматы с одной компонентой связности, определяющие заданный регулярный язык.
Разработка математической модели, которая представляет собой структуру на множестве специально определяемых состояний. Каждое
^"Будем говорить, что один детерминированный автомат является «большим» по отношению к другому детерминированному автомату тогда и только тогда, когда он имеет большее количество состояний, чем другой детерминированный автомат. Тогда другой детерминированный автомат будем называть «меньшим». Если автоматы имеют равное количество состояний, то любой из них будем называть «большим». Данные понятия используются далее.
из них содержит подмножество множества блоков, включающее все элементы множества бинарного отношения #, а также всё множество циклов (соответствующих циклам базисного автомата), которое описывается специальным образом, например, с помощью регулярных выражений.
6. Демонстрация с помощью примеров, что новые модели и предложенные доказательства помогают разработать более эффективные алгоритмы минимизации (в первую очередь эвристические) и вспомогательные алгоритмы к ним.
Апробация работы. Основные научные и практические результаты исследований по теме диссертации докладывались на:
XVIII Международной научно-технической конференции «Математические методы и информационные технологии в экономике, социологии и образовании» (г. Пенза, 2006);
XXI Международной научно-технической конференции «Математические методы и информационные технологии в экономике, социологии и образовании» (г. Пенза, 2008);
семинаре кафедры математического анализа физико-математического факультета ГОУ УлГПУ им. И. Н. Ульянова (г. Ульяновск, 2009).
Всероссийской конференции «Проведение научных исследований в области обработки, хранения, передачи и защиты информации» (г. Ульяновск, 2009).
Личный вклад. Изложенные теоремы доказаны лично автором, либо совместно с научным руководителем. При этом части доказательств, связанные с базисным автоматом, а также с операциями дублирования и объединения состояний конечного автомата, принадлежат автору диссертации. Построение двух моделей эквивалентных преобразований конечных автоматов выполнено автором диссертации самостоятельно.
Публикации. Основные результаты диссертации опубликованы в 6 работах, 2 из которых входят в список изданий, рекомендованных ВАК.
Структура и объем диссертации. Общий объем диссертации - 115 страниц. Диссертация состоит из введения, четырех глав, заключения, списка используемой литературы из 83 наименований и одного приложения.
Похожие диссертации на Некоторые алгоритмы эквивалентного преобразования недетерминированных конечных автоматов
