Введение в теорию конечных автоматов: Пер. с нем. — М.: Радио и связь, 1987. — 392 с.: ил.
В книге профессора Гамбургского университета описаны основные классические модели теории конечных автоматов (автоматы Мили и Мура) и более сложные модели (автоматы Рабина — Скотта, многоленточные автоматы, конечные преобразователи). Рассмотрены преобразования конечных автоматов и регулярные множества. Существенную часть книги составляют упражнения.
Для инженерно-технических работников, связанных с приложениями теории конечных автоматов, а также работающих в области информатики и вычислительной техники.
ПРЕДИСЛОВИЕ
Конечные автоматы и такие тесно связанные с ними конструкции, как, например, линейные грамматики и регулярные выражения, относятся к важнейшим основным понятиям информатики. Различные варианты конечных автоматов и близкие им математические объекты служат для описания и анализа технических устройств, различных систем и процессов, программ и алгоритмов. Многие сложные концепции теоретической информатики — и при-том относящиеся не только к более общим моделям автоматов, таким как автоматы с магазинной памятью и машины Тьюринга, — были выработаны на базе теории конечных автоматов. Теория автоматов порождает ряд легко формулируемых, но далеко не тривиальных проблем. Они приводят к весьма сложным алгоритмам и отчасти проясняют причины, по которым необходимо систематическое развитие математического программирования и теории алгоритмов, сопровождаемое подробным анализом корректности и сложности. Теория конечных автоматов имеет многочисленные приложения в технической и практической информатике и составляет существенную часть теоретической информатики. Это делает знание основ теории автоматов необходимым каждому специалисту по информатике.
Данная книга дает начальные представления о важнейших классических основных моделях, концепциях, методах и результатах теории конечных автоматов.
Поскольку теория автоматов является одним из старейших разделов теоретической информатики, широко развитым во многих направлениях, возможны целый ряд подходов низложение разных аспектов этой теории различными методами и с различными целями. В данной книге избран «средний путь» между чисто математическим и направленным только на ^приложения подходами.
Мы будем рассматривать конечные автоматы как абстрактные модели простейших устройств, обрабатывающих данные, обращая в основном внимание на входно-выходное поведение, т. е. на определяемое автоматом отображение или соответствие между входным и выходным множествами слов. При этом особое значение будет придаваться конструктивным и алгоритмическим аспектам проблемы.
Способ изложения ориентирован прежде всего на теорию формальных языков, однако не предполагается, что у читателя имеются какие-либо специальные познания в этой области. Кроме
S
ОГЛАВЛЕНИЕ
Предисловие ................. 5
Глава 1. Основные математические понятия........ 8
Введение .................. 8
1.1. Множества................. "
1.2. Соответствия и отображения............ 14
1.3. Отношения и графы.............. '8
1.4. Моноиды и гомоморфизмы............ 23
1.5. Методы доказательств.............. 29
Глава 2. Автоматы Мили............. 33
2.1. Вводный пример................ 33
2.2. Определение, пример и контрпример.......... 36
2.3. Реакция, эквивалентность, сокращение......... 37
2.4. О способе определения эквивалентности состояний...... 41
2.5. Метод Хопкрофта — Гриса............ 45
2.6. Различимость входных последовательностей....... 58
2.7. Автоматы Мили с конечной памятью......... 64
Упражнения ................. 67
Обзор литературы............... 70
Глава 3. Автоматы Мура............. 71
3.1. Вводный пример..............
3.2. Определение и первое сравнение с автоматами Мили..... 74
3.3. Реакция, эквивалентность, сокращение......... 77
3.4. Равносильность автоматов Мили и Мура..... . . 79
3.5. Дальнейшие примеры.............. 82
3.6. Гомоморфизмы и изоморфизмы........... 85
3.7. Аппроксимация отображений............ 89
3.8. Эксперименты................ 96
3.9. Однократные ' автономные диагностические эксперименты с дополнительной информацией ............. 101
Упражнения................ И2
Обзор литературы............... 117
Глава 4. Частичные автоматы Мили.......... 118
4.1. Вводные примеры............... 118
4.2. Определение, различные понятия реакции и эквивалентности, совместность ................. 12Г)
4.3. Доопределение и сокращение............ 132
4.4. Покрытие и минимизация............. 137
4.5. Алгебраическая постановка проблемы минимизации..... 145
Упражнения................ 153
Обзор литературы.............. 157
Глава 5. Автоматы Рабина — Скотта.......... 158
5.1. Вводные примеры............... 158
5.2. Недетерминированные автоматы Рабина — Скотта (НРС-автоматы) 168
5.3. Реакция, допустимые множества .......... 175
391
5.4. Детерминированные автоматы и различимые множества .... 185
5.5. Эквивалентность различных понятий.......... ^
5.6. Равенства и системы равенств . . _........ 201
5.7. Рациональные выражения............ j-**
Упражнения........•........ 224
Обзор литературы............... 231
Глава 6. Преобразования автоматов.......... 232
6.1. Вводные примеры............... 233
6.2. Преобразование НРС-автомата в PC-автомат....... "37
6.3. Минимизация детерминированных автоматов....... 243
6.4. Проблема минимизации для НРС-автоматов....... 251
6.5. Методы уменьшения числа состояний......... 257
6.6. Частные и производные............. 261
Упражнения................ 268
Обзор литературы............... 274
Глава 7. Дальнейшие характеризации допустимых множеств .... 274
7.1. Последовательности вычислений программ, схемы Янова .... 275
7.2. Графы Майхилла............... 279
7.3. Стандартные множества............. 285
7.4. Двусторонние автоматы............. 289
7.5. Автоматы с предварительным просмотром........ 297
7.6. Матричные представления............. 302
7.7. НРС-автоматы с одноэлементным входным алфавитом..... 304
Упражнения.................306
Обзор литературы............... 310
Глава 8. Преобразователи и двуленточные автоматы...... 310
8.1. Ретроспекция................ 310
8.2. а-преобразователи............... 313
8.3. Неразрешимость проблемы эквивалентности а-иреовразователей . . 322
8.4. Двуленточные автоматы Элго — Мезея......... 328
8.5. Двуленточные автоматы Элго — Эйленберга — Шефердсона . . . 335
8.6. Детерминированные двуленточные автоматы....... 339
8.7. Двуленточные автоматы Рабина — Скотта........ 351
8.8. Обобщения................ 358
Упражнения................ 364
Обзор литературы............... 371
Список литературы.............. 373
Список работ советских авторов и работ, переведенных на русский
язык.................. 386
Предметный указатель............. 387
Цена: 150руб.
