Мультиэвристический подход к звёздно-высотной минимизации недетерминированных конечных автоматов

• Автор: Баумгертнер, Светлана Викторовна
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Тольятти
• Количество страниц: 123 с. : ил.

Содержание
Глава 1. Введение
1.1. Подходы к решению задач дискретной оптимизации
1.2. Основные вопросы и результаты, связанные с проблемой звёздной высоты
1.3. Актуальность темы
Глава 2. Фундаментальные понятия предметной области
2.1. Формальные языки и конечные автоматы
2.2. Регулярные выражения
2.3. Звёздная высота регулярных выражений
2.4. Метод ветвей и границ
Глава 3. Эквивалентность конечных автоматов и регулярных выражений. Специальное доказательство теоремы Клини
3.1. Построение конечного автомата, эквивалентного заданному регулярному выражению
3.2. Построение регулярного выражения, эквивалентного заданному конечному автомату. Теорема Клини
Глава 4. Преобразование конечного автомата к регулярному выражению. Точный алгоритм построения оптимального регулярного выражения по заданному конечному автомату
4.1. Метод последовательного удаления вершин
4.2. Задача звёздно-высотной минимизации недетерминированного конечного автомата в терминах дискретного программирования
4.3. Метод оптимизированного полного перебора
Глава 5. Эвристические алгоритмы для приближённого решения задачи поиска псевдооптимального регулярного выражения по конечному автомату
Глава 6. Методы усреднения эвристик. Динамические оценки состояний автомата
Глава 7. Апуйте-алгоритм

звёздно-высотной минимизации недетерминированного конечного автомата
7.1 Незавершённый метод ветвей и границ
7.2 Пошаговое описание апуйте-алгоритма
Глава 8. Обобщённые конечные автоматы и обобщённые регулярные выражения. Алгоритм построения
обобщённого регулярного выражения для заданного
обобщённого конечного автомата
8.1. Основные определения
8.2. Алгоритм построения обобщённого регулярного выражения, эквивалентного обобщённому конечному автомату
Глава 9. Описание вычислительных экспериментов и их результатов
9.1. Алгоритм генерации случайного конечного автомата
9.2. Результаты вычислительных экспериментов
Глава 10. Описание программной реализации
разработанных алгоритмов
Заключение
Приложение
Литература
Глава 1. Введение
Понятие регулярного языка играет важнейшую роль в современной информатике - причём как в теоретических, так и практических её разделах. Регулярные языки являются важным классом формальных языков. Они нашли широкое применение в различных приложениях. Это, например, лексический и синтаксический анализ, текстовые редакторы, программы обработки текста и форматированного вывода на печать, сопоставления с образцом, языки запросов, информационнопоисковые системы и др.
При этом в различных приложениях желательно использовать разные способы представления регулярного языка - а для каждого из этих способов очень часто важным является максимально экономичное задание.
Существуют, по крайней мере, три задачи минимизации недетерминированных конечных автоматов. Например, задача вершинной минимизации - это задача построения конечного автомата, определяющего заданный регулярный язык и имеющего минимально возможное количество вершин. Аналогично определяются задачи дуговой и звёздновысотной минимизации. Можно считать, что задача звёздно-высотной минимизации конечного автомата заключается в уменьшении вложенности циклов графа переходов автомата [74].
В некоторых областях теории формальных языков (например, языки программирования) желательно использование регулярных выражений с минимально возможной вложенностью операции * («звезда Кли-ни»). Таким образом, возникает задача минимизации регулярного выражения по вложенности операции *. Эта характеристика структурной сложности регулярного выражения называется звёздной высотой.

Глава 4. Преобразование конечного автомата к регулярному выражению.
Точный алгоритм построения оптимального регулярного выражения по заданному конечному автомату
4.1. Метод последовательного удаления вершин
Данный метод был предложен в [84]. Он позволяет построить регулярное выражение по заданному конечному автомату. Отметим, что полученное регулярное выражение, вообще говоря, не является оптимальным с точки зрения звёздной высоты.
В этом методе на каждом шаге из конечного автомата удаляется одно состояние, а все данные о связанных с ним переходах добавляются в новые переходы между оставшимися состояниями автомата. Процедура удаления состояний повторяется до тех пор, пока мы не получим конечный автомат, в котором присутствуют только стартовое состояние, финальное состояние и переход между ними, помеченный искомым регулярным выражением.
Здесь будем использовать конечный автомат, вторым параметром в функции переходов которого будем считать не букву алфавита, а некоторое регулярное выражение <5 : £>х (а) -> Р(0.
Алгоритм состоит из следующих шагов:
1. К автомату добавляются новое стартовое (5) и новое финальное (А) состояния, 5' соединяется со всеми стартовыми состояниями исходного автомата переходами, помеченными пустым символом е. Анало-