В книге профессора Гамбургского университета описаны основные классические модели теории конечных автоматов (автоматы Мили и Мура) и более сложные модели (автоматы Рабина — Скотта, многоленточные автоматы, конечные преобразователи). Рассмотрены преобразования конечных автоматов и регулярные множества. Существенную часть книги составляют упражнения.
Для инженерно-технических работников, связанных с приложениями теории конечных автоматов, а также работающих в области информатики и вычислительной техники.
Author(s): Брауэр В.
Publisher: Радио и связь
Year: 1987
Language: Russian
Pages: 392
City: Москва
Предисловие ......Page 6
Введение ......Page 9
1.1. Множества ......Page 10
1.2. Соответствия и отображения ......Page 15
1.3 Отношения и графы ......Page 19
1.4. Моноиды и гомоморфизмы ......Page 24
1.5. Методы доказательств ......Page 30
2.1. Вводный пример ......Page 34
2.2. Определение, пример и контрпример ......Page 37
2.3 Реакция, эквивалентность, сокращение ......Page 38
2.4. О способе определения эквивалентности состояний ......Page 42
2.5. Метод Хопкрофта — Гриса ......Page 46
2.6. Различимость входных последовательностей ......Page 59
2.7. Автоматы Мили с конечной памятью ......Page 65
Упражнения ......Page 68
Обзор литературы ......Page 71
3.1. Вводный пример ......Page 72
3.2. Определение и первое сравнение с автоматами Мили ......Page 75
3.3. Реакция, эквивалентность, сокращение ......Page 78
3.4. Равносильность автоматов Мили и Мура ......Page 80
3.5 Дальнейшие примеры ......Page 83
3.6. Гомоморфизмы и изоморфизмы ......Page 86
3.7. Аппроксимация отображений ......Page 90
3.8. Эксперименты ......Page 97
3.9. Однократные автономные диагностические эксперименты с дополнительной информацией ......Page 102
Упражнения ......Page 113
Обзор литературы ......Page 118
4.1 Вводные примеры ......Page 119
4.2 Определение, различные понятия реакции и эквивалентности, совместность ......Page 126
4.3. Доопределение и сокращение ......Page 133
4.4. Покрытие и минимизация ......Page 138
4.5. Алгебраическая постановка проблемы минимизации ......Page 146
Упражнения ......Page 154
Обзор литературы ......Page 158
5.1. Вводные примеры ......Page 159
5.2 Недетерминированные автоматы Рабина — Скотта (НРС-автоматы) ......Page 169
5.3. Реакция, допустимые множества ......Page 176
5.4. Детерминированные автоматы и различимые множества ......Page 186
5.5. Эквивалентность различных понятий ......Page 195
5.6. Равенства и системы равенств ......Page 202
5.7. Рациональные выражения ......Page 213
Упражнения ......Page 225
Обзор литературы ......Page 232
Глава 6. Преобразования автоматов ......Page 233
6.1. Вводные примеры ......Page 234
6.2. Преобразование НРС-автомата в PC-автомат ......Page 238
6.3. Минимизация детерминированных автоматов ......Page 244
6.4. Проблема минимизации для НРС-автоматов ......Page 252
6.5. Методы уменьшения числа состояний ......Page 258
6.6. Частные и производные ......Page 262
Упражнения ......Page 269
Глава 7. Дальнейшие характеризации допустимых множеств ......Page 275
7.1. Последовательности вычислений программ, схемы Янова ......Page 276
7.2. Графы Майхнлла ......Page 280
7.3. Стандартные множества ......Page 286
7.4. Двусторонние автоматы ......Page 290
7.5. Автоматы с предварительным просмотром ......Page 298
7.6. Матричные представления ......Page 303
7.7. НРС-автоматы с одноэлементным входным алфавитом ......Page 305
Упражнения ......Page 307
8.1. Ретроспекция ......Page 311
8.2. а-преобразователи ......Page 314
8.3. Неразрешимость проблемы эквивалентности а-преооразователей ......Page 323
8.4. Двуленточные автоматы Элго — Мезея ......Page 329
8.5. Двуленточные автоматы Элго — Эйленберга — Шефердсона ......Page 336
8.6. Детерминированные двуленточные автоматы ......Page 340
8.7. Двуленточные автоматы Рабина — Скотта ......Page 352
8.8. Обобщения ......Page 359
Упражнения ......Page 365
Обзор литературы ......Page 372
Список литературы ......Page 374
Список работ советских авторов и работ, переведенных на русский язык ......Page 387
Предметный указатель ......Page 388
