Некоторые алгоритмы эквивалентного преобразования недетерминированных конечных автоматов

• Автор: Зузанова, Мария Рафаэльевна
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Тольятти
• Количество страниц: 115 с. : ил.

Оглавление
1 Введение

1.1 Фундаментальные достижения теории формальных языков и автоматов.

1.2 Основное содержание работы.

1.3 Области применения регулярных языков и

конечных автоматов

1.4 Фундаментальные понятия теории формальных языков и автоматов

1.5 Конечные автоматы и операции над ними

2 Алгоритмы эквивалентного преобразования автоматов

2.1 Операции объединения и дублирования состояний

конечного автомата

2.2 Построение эквивалентного конечного автомата для любого заданного с помощью базисного
2.3 Некоторые примеры
3 Модели эквивалентных преобразований недетерминированных конечных автоматов
3.1 Модель построения любого конечного автомата из заданного
с иомощыо базисного автомата
3.2 Модель поиска минимальное подмножества
множества блоков
4 Бинарное отношение , его свойства и минимизация
4.1 Бинарное отношение и его свойства
4.2 Заключение. Псжоторые вопросы минимизации
Литература


При этом части доказательств, связанные с базисным автоматом, а также с операциями дублирования и объединения состояний конечного автомата, принадлежат автору диссертации. Построение двух моделей эквивалентных преобразований конечных автоматов выполнено автором диссертации самостоятельно. Публикации. Основные результаты диссертации опубликованы в 5 работах. ВАК. Структура и объем диссертации. Общий объем диссертации - 5 страниц. Диссертация состоит из введения, четырех глав, заключения, списка используемой литературы из наименований и одного приложения. Первая глава является введением, в ней приводятся общий обзор диссертационной работы, краткое содержание глав. Кроме этого, описаны фундаментальные достижения, сделанные зарубежными и отечественными учёными в этой области. Также приведены Фундаментальные понятия, определения и теоремы теорий формальных языков и автоматов. В первой главе диссертации также рассматриваются области применения конечных автоматов и регулярных языков, приводятся примеры. Отмечается, что для того, чтобы эго применение конечных автоматов на практике было более эффективным, желательно, чтобы количество состояний автомата и переходов между ними было сравнительно невелико. Поэтому решение проблемы вершинной минимизации конечного автомата, частично рассматриваемой в данной работе, является важным не только для теории, но и для практики. Предметной областью данной работы являются регулярные языки и конечные автоматы, которые относятся к старейшим разделам теории формальных языков. Толчком для систематического изучения регулярных языков и конечных автоматов можно по праву считать тот факт, что Мак-Каллок и Питтс применяли машины с конечным числом состояний для моделирования нейронных сетей в первой половине сороковых годов XX века (см. Разработкой алгоритмов, в чём-то аналогичных алгоритмам, сформулированным в виде нескольких теорем во второй главе данной работы, занимаются также п зарубежные авторы. Напрнмер, такие алгоритм 1,1 можно найти в работе ||. С тех пор они были широко изучены н применялись в различных областях науки. Одним из самых ранних и значительных вкладов в этой сфере является теорема Клшш, благодаря которой учёный доказал эквивалентность регулярных выражений и конечных автоматов. Также Клини сформулировал определение регулярных выражений в году. Неоценимый вклад в теорию автоматов внесли Майкл Рабин и Дана Скотт, которые предложили формализм «недетерминированный конечный автомат* в своей работе «Конечные автоматы и проблема разрешимости для них» (см. Их статья стала классической в теории автоматов и являлась источником вдохновения для многих последующих работ в этой области и принесла авторам премию Тыориига. Во многих странах считается, что они были первыми, кто описал недетерминированные конечные автоматы в вышеупомянутой работе. Однако существует мнение, что первым описал э тот формализм советский учёный Медведев. Этот факт подтверждает то, что работа Медведева, о недетерминированных конечных автоматах (см. Рабина и Скотта. Они никогда не оспаривали этот факт и утверждали, что они были не единственными, кто работал в этой области, но именно им удалось сфор^лировать основные идеи. Кроме того, Рабин и Скотт в одной из своих статей описали свойства замкнутости регулярных множеств и доказали теорему о разрешимости. Также одними из ранних достижений в этой области являются неоднозначно дейс твующие при прочтении цепочки, конечные автоматы с выводом, рассмотренные Мили и Муром (см. Майхиллом н Нсроудом характеризация регулярных языков. Хафмеи (5-1) и Мур () были первыми, кто стал изучать минимизацию конечного автомата. Множество учёных заинтересовал этот вопрос, и до сих пор он изучается с большим интересом. Гинзбург и Пратер рассматривали проблему того, что существует много методов минимизации не полностью определенного конечною автомата. Значительный вклад внёс профессор Массачуссетского технологического института Ноам Хомский в теорию языков и автоматов. Теорему Клини и её доказательство можно найти в || и в []).