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

ID: 43810
Дата закачки: 11 Февраля 2011
Продавец: GnobYTEL (Напишите, если есть вопросы)
Посмотреть другие работы этого продавца

Тип работы: Книга

Описание:
ОТ РЕДАКТОРА ПЕРЕВОДА 5
ПРЕДИСЛОВИЕ 5
ГЛАВА 1. ОСНОВНАЯ МОДЕЛЬ 8
1.1. Введение 8
1.2. Многополюсный черный ящик 8
1.3. Дискретность времени 9
1.4. Конечность алфавита 10
1.5. Состояния 11
1.6. Определение основной модели 13
1.7. Примеры конечных автоматов 14
1.8. Определение множества состояний по внутренней структуре 15
1.9. Другая модель 16
1.10. Предсказание поведения автомата 18
ГЛАВА 2 21
ТАБЛИЦЫ, ГРАФЫ И МАТРИЦЫ ПЕРЕХОДОВ 21
2.1. Введение 21
2.2. Таблица переходов 21
2.4. Изоморфные автоматы 23
2.5. Граф переходов 24
2.6. Классификация состояний и подавтоматов 26
2.7. Разложение автоматов и расщепляемый автомат 29
2.8. Матрица переходов 32
2.9. Матрицы переходов высшего порядка 34
2.10. Элементарные пути 36
2.11. Определение минимальных путей и полных контуров 38
2.12. Скелетная матрица 40
2.13. Частичное построение матриц 43
Задачи 44
ГЛАВА 3 48
ЭКВИВАЛЕНТНОСТЬ И МИНИМИЗАЦИЯ АВТОМАТОВ 48
3.1. Введение 48
3.2. Эквивалентность состояний 48
3.3. k-эквивалентность 50
3.4. k-эквивалентные разбиения 52
3.5. Эквивалентные разбиения 55
8.6. Разбиение при помощи таблиц Рk 57
3.7. Разбиение при помощи таблицы пар 59
8.8. Матричный метод разбиения 62
3.9. Эквивалентность автоматов 64
8.10. Эквивалентное разбиение множеств автоматов 65
3.11. Минимальная форма 68
3.12. Свойства минимальной формы 70
3.13. Уменьшение числа состояний автомата последовательным объединением 72
3.14. Класс минимальных автоматов 74
Задачи 75
ГЛАВА 4 78
ЭКСПЕРИМЕНТЫ ПО РАСПОЗНАВАНИЮ СОСТОЯНИЙ 78
4.1. Введение 78
4.2. Классификация экспериментов 79
4.3. Диагностические и установочные эксперименты 80
4.4. Диагностические эксперименты для двух состояний 81
4.5. Разновидности диагностической задачи с двумя состояниями 85
4.6. Дерево преемников 87
4.7. Диагностическое дерево 88
4.8. Простые безусловные диагностические эксперименты 91
4.9. Простые условные диагностические эксперименты 92
4.10. Кратные безусловные диагностические эксперименты 96
4.11. Кратные условные диагностические эксперименты 100
4.12. Установочное дерево 102
4.13. Простые безусловные установочные эксперименты 104
4.14. Простые условные установочные эксперименты 105
4.15. Регулярные безусловные установочные эксперименты 106
4.16. Регулярные условные установочные эксперименты 108
4.17. Следствия, связанные с экспериментами по распознаванию состояний 111
Задачи 113
ГЛАВА 5 117
ЭКСПЕРИМЕНТЫ ПО РАСПОЗНАВАНИЮ АВТОМАТОВ 117
5.1. Введение 117
5.2. Общая задача распознавания автомата 118
5.3. Распознавание автоматов известного класса 119
5.4. Задача распознавания повреждений 122
5.5, Сильносвязные автоматы 125
5.6. Некоторые свойства сильносвязных автоматов 126
5.7. Распознавание сильносвязных (n, р, q)-автоматов 127
5.8. Автоматы без потери информации 128
Задачи 132
ГЛАВА 6 134
АВТОМАТЫ С КОНЕЧНОЙ ПАМЯТЬЮ 134
6.1. Введение 134
6.2. Представление систем с конечной памятью 135
6.3. Свойства автоматов с конечной памятью 137
6.4. Определение памяти автомата 140
6.5. Минимальная x-z-функция 142
6.6. Линейные двоичные автоматы 145
6.7. Временная характеристика линейного двоичного автомата 149
6.8. Распознавание линейного двоичного автомата 151
6.9. Не зависящие от выхода автоматы 153
Задачи 156
ГЛАВА 7 158
АВТОМАТЫ С ОГРАНИЧЕНИЯМИ НА ВХОДЕ 158
7.1. Введение 158
7.2. Совместимость состояний 159
7.3. Квазиэквивалентные автоматы 161
7.4. Определение минимальных форм 162
7.5. Метод уменьшения числа состояний автоматов с ограничениями на входе 165
Задачи 168
БИБЛИОГРАФИЯ 169
Предлагаемая книга Артура Гилла – доктора наук по электротехнике, преподавателя Калифорнийского университета – содержит систематическое изложение основных вопросов теории конечных автоматов.
В книге дается строгое определение конечного автомата, как модели реального устройства, с иллюстрацией на примерах. Автор, сохраняя математическую строгость, в доступной для широкого круга читателей форме, ясно и последовательно излагает различные способы представления конечных автоматов (таблицы, графы, матрицы переходов), методы минимизации автоматов, теорию экспериментов над автоматами и ряд других вопросов. Принятое расположение материала облегчает его усвоение инженерно-техническими работниками, имеюимеющими дело с реальными объектами, так как при абстрактном представлении позволяет сохранять связь с привычными для инженера реальными устройствами. Основным отличием книги от существующих является подробное и систематическое изложение достижений в области теории экспериментов, которая начинает находить широкое применение при решении задач технической диагностики дискретных устройств и систем с памятью, в том числе вычислительных и управляющих машин.
Каждая глава книги содержит примеры и заканчивается задачами, что облегчает глубокую проработку и усвоение ее содержания.
Книга является хорошим учебным пособием для студентов, инженеров и научных работников, занимающихся изучением теории конечных автоматов и ее практическими приложениями.

Размер файла: 21 Мбайт
Фаил: