Введение в теорию конечных автоматов

  

Гилл А. Введение в теорию конечных автоматов. М.: Наука, 1966. - 272 с.

Предлагаемая книга Артура Гилла—доктора наук по электротехнике, преподавателя Калифорнийского университета — содержит систематическое изложение основных вопросов теории конечных автоматов. Особое внимание в книге уделено методам анализа. Вопросы синтеза конечных автоматов здесь не рассматриваются.

Каждая глава книги содержит примеры и заканчивается задачами, что облегчает глубокую приработку и усвоение ее содержания.

Книга является хорошим учебным пособием для студентов, инженеров и научных работников, занимающихся изучением теории конечных автоматов и ее практическими приложениями.



Оглавление

ОТ РЕДАКТОРА ПЕРЕВОДА
ПРЕДИСЛОВИЕ
ГЛАВА 1. ОСНОВНАЯ МОДЕЛЬ
1.2. Многополюсный черный ящик
1.3. Дискретность времени
1.4. Конечность алфавита
1.5. Состояния
1.6. Определение основной модели
1.7. Примеры конечных автоматов
1.8. Определение множества состояний по внутренней структуре
1.9. Другая модель
1.10. Предсказание поведения автомата
Задачи
ГЛАВА 2. ТАБЛИЦЫ, ГРАФЫ И МАТРИЦЫ ПЕРЕХОДОВ
2.2. Таблица переходов
2.3. Перечисление автоматов
2.4. Изоморфные автоматы
2.5. Граф переходов
2.6. Классификация состояний и подавтоматов
2.7. Разложение автоматов и расщепляемый автомат
2.8. Матрица переходов
2.9. Матрицы переходов высшего порядка
2.10. Элементарные пути
2.11. Определение минимальных путей и полных контуров
2.12. Скелетная матрица
2.13. Частичное построение матриц
Задачи
ГЛАВА 3. ЭКВИВАЛЕНТНОСТЬ И МИНИМИЗАЦИЯ АВТОМАТОВ
3.2. Эквивалентность состояний
3.3. k - эквивалентность
3.4. k-эквивалентные разбиения
3.5. Эквивалентные разбиения
3.6. Разбиение при помощи таблиц
3.7. Разбиение при помощи таблицы пар
3.8. Матричный метод разбиения
3.9. Эквивалентность автоматов
3.10. Эквивалентное разбиение множеств автоматов
3.11. Минимальная форма
3.12. Свойства минимальной формы
3.13. Уменьшение числа состояний автомата последовательным объединением
3.14. Класс минимальных автоматов
Задачи
ГЛАВА 4. ЭКСПЕРИМЕНТЫ ПО РАСПОЗНАВАНИЮ СОСТОЯНИЙ
4.2. Классификация экспериментов
4.3. Диагностические и установочные эксперименты
4.4. Диагностические эксперименты для двух состояний
4.5. Разновидности диагностической задачи с двумя состояниями
4.6. Дерево преемников
4.7. Диагностическое дерево
4.8. Простые безусловные диагностические эксперименты
4.9. Простые условные диагностические эксперименты
4.10. Кратные безусловные диагностические эксперименты
4.11. Кратные условные диагностические эксперименты
4.12. Установочное дерево
4.13. Простые безусловные установочные эксперименты
4.14. Простые условные установочные эксперименты
4.16. Регулярные безусловные установочные эксперименты
4.16. Регулярные условные установочные эксперименты
4.17. Следствия, связанные с экспериментами по распознаванию состояний
Задачи
ГЛАВА 5. ЭКСПЕРИМЕНТЫ ПО РАСПОЗНАВАНИЮ АВТОМАТОВ
5.2. Общая задача распознавания автомата
5.3. Распознавание автоматов известного класса
5.4. Задача распознавания повреждений
5.5. Сильносвязные автоматы
5.6. Некоторые свойства сильносвязных автоматов
5.7. Распознавание сильносвязных (n, p, q)-автоматов
5.8. Автоматы без потери информации
Задачи
ГЛАВА 6. АВТОМАТЫ С КОНЕЧНОЙ ПАМЯТЬЮ
6.2. Представление систем с конечной памятью
6.3. Свойства автоматов с конечной памятью
6.4. Определение памяти автомата
6.5. Минимальная x-z-функция
6.6. Линейные двоичные автоматы
6.7. Временная характеристика линейного двоичного автомата
6.8. Распознавание линейного двоичного автомата
6.9. Не зависящие от выхода автоматы
Задачи
ГЛАВА 7. АВТОМАТЫ С ОГРАНИЧЕНИЯМИ НА ВХОДЕ
7.2. Совместимость состояний
7.3. Квазиэквивалентные автоматы
7.4. Определение минимальных форм
7.5. Метод уменьшения числа состояний автоматов с ограничениями на входе
Задачи
БИБЛИОГРАФИЯ