Введение в теорию конечных автоматов
Артур Гилл
Предлагаемая книга Артура Гилла (доктора наук по электротехнике, преподавателя Калифорнийского университета) содержит систематическое изложение основных вопросов теории конечных автоматов.
В книге дается строгое определение конечного автомата как модели реального устройства, с иллюстрацией на примерах. Автор, сохраняя математическую строгость, в доступной для широкого круга читателей форме, ясно и последовательно излагает различные способы представления конечных автоматов (таблицы, графы, матрицы переходов), методы минимизации автоматов, теорию экспериментов над автоматами и ряд других вопросов. Принятое расположение материала облегчает его усвоение инженерно-техническими работниками, имеющими дело с реальными объектами, так как при абстрактном представлении позволяет сохранять связь с привычными для инженера реальными устройствами. Основным отличием книги от существующих является подробное и систематическое изложение достижений в области теории экспериментов, которая начинает находить широкое применение при решении задач технической диагностики дискретных устройств и систем с памятью, в том числе вычислительных и управляющих машин.
Каждая глава книги содержит примеры и заканчивается задачами, что облегчает глубокую проработку и усвоение ее содержания.
Книга является хорошим учебным пособием для студентов, инженеров и научных работников, занимающихся изучением теории конечных автоматов и ее практическими приложениями.
Серия «Теоретические основы технической кибернетики».
М., 1966 г.
Количество страниц: 272.
Содержание книги «Введение в теорию конечных автоматов»:
- 8 От редактора перевода
- 9 Предисловие
- 13 Глава 1. Основная модель
- 13 1.1. Введение
- 13 1.2. Многополюсный черный ящик
- 15 1.3. Дискретность времени
- 17 1.4. Конечность алфавита
- 19 1.5. Состояния
- 21 1.6. Определение основной модели
- 22 1.7. Примеры конечных автоматов
- 24 1.8. Определение множества состояний по внутренней структуре
- 27 1.9. Другая модель
- 29 1.10. Предсказание поведения автомата
- 31 Задачи
- 34 Глава 2. Таблицы, графы и матрицы переходов
- 34 2.1. Введение
- 34 2.2. Таблица переходов
- 37 2.3. Перечисление автоматов
- 38 2.4. Изоморфные автоматы
- 40 2.5. Граф переходов
- 43 2.6. Классификация состояний и подавтоматов
- 47 2.7. Разложение автоматов и расщепляемый автомат
- 52 2.8. Матрица переходов
- 55 2.9. Матрицы переходов высшего порядка
- 58 2.10. Элементарные пути
- 61 2.11. Определение минимальных путей и полных контуров
- 65 2.12. Скелетная матрица
- 68 2.13. Частичное построение матриц
- 70 Задачи
- 75 Глава 3. Эквивалентность и минимизация автоматов
- 75 3.1. Введение
- 76 3.2. Эквивалентность состояний
- 79 3.3. k-эквивалентность
- 82 3.4. k-эквивалентные разбиения
- 87 3.5. Эквивалентные разбиения
- 90 3.6. Разбиения при помощи таблиц Pk
- 92 3.7. Разбиение при помощи таблицы пар
- 97 3.8. Матричный метод разбиения
- 100 3.9. Эквивалентность автоматов
- 102 3.10. Эквивалентное разбиение множеств автоматов
- 106 3.11. Минимальная форма
- 110 3.12. Свойства минимальной формы
- 113 3.13. Уменьшение числа состояний автомата последовательным объединением
- 116 3.14. Класс минимальных автоматов
- 118 Задачи
- 122 Глава 4. Эксперименты по распознаванию состояний
- 122 4.1. Введение
- 123 4.2. Классификация экспериментов
- 125 4.3. Диагностические и установочные эксперименты
- 126 4.4. Диагностические эксперименты для двух состояний
- 132 4.5. Разновидности диагностической задачи с двумя состояниями
- 135 4.6. Дерево преемников
- 138 4.7. Диагностическое дерево
- 143 4.8. Простые безусловные диагностические эксперименты
- 145 4.9. Простые условные диагностические эксперименты
- 151 4.10. Кратные безусловные диагностические эксперименты
- 159 4.11. Кратные условные диагностические эксперименты
- 161 4.12. Установочное дерево
- 164 4.13. Простые безусловные установочные эксперименты
- 165 4.14. Простые условные установочные эксперименты
- 168 4.15. Регулярные безусловные установочные эксперименты
- 171 4.16. Регулярные условные установочные эксперименты
- 176 4.17. Следствия, связанные с экспериментами по распознаванию состояний
- 178 Задачи
- 184 Глава 5. Эксперименты по распознаванию автоматов
- 184 5.1. Введение
- 185 5.2. Общая задача распознавания автомата
- 188 5.3. Распознавание автоматов известного класса
- 192 5.4. Задача распознавания повреждений
- 196 5.5. Сильносвязные автоматы
- 198 5.6. Некоторые свойства сильносвязных автоматов
- 200 5.7. Распознавание сильносвязных (n, p, q)-автоматов
- 201 5.8. Автоматы без потери информации
- 207 Задачи
- 210 Глава 6. Автоматы с конечной памятью
- 210 6.1. Введение
- 211 6.2. Представление систем с конечной памятью
- 215 6.3. Свойства автоматов с конечной памятью
- 220 6.4. Определение памяти автомата
- 222 6.5. Минимальная x-y-функция
- 227 6.6. Линейные двоичные автоматы
- 232 6.7. Временная характеристика линейного двоичного автомата
- 237 6.8. Распознавание линейного двоичного автомата
- 240 6.9. Не зависящие от выхода автоматы
- 243 Задачи
- 247 Глава 7. Автоматы с ограничениями на входе
- 247 7.1. Введение
- 248 7.2. Совместимость состояний
- 251 7.3. Квазиэквивалентные автоматы
- 254 7.4. Определение минимальных форм
- 259 7.5. Метод уменьшения числа состояний автоматов с ограничениями на входе
- 262 Задачи
- 265 Библиография
- 269 Предметный указатель
Инструкция как скачать книгу Артур Гилл: Введение в теорию конечных автоматов в форматах DjVu, PDF, DOC или fb2 совершенно бесплатно.
