Гилл А. — Введение в теорию конечных автоматов :: Электронная библиотека попечительского совета мехмата МГУ

Главная Ex Libris Книги Журналы Статьи Серии Каталог Wanted Загрузка ХудЛит Справка Поиск по индексам Поиск Форум

Авторизация

Поиск по указателям

Красота

Гилл А. — Введение в теорию конечных автоматов

Гилл А. — Введение в теорию конечных автоматов

Обсудите книгу на научном форуме

Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter

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

Автор: Гилл А.

Аннотация:

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

Язык:

Рубрика: Computer science/Алгоритмы/

Статус предметного указателя: Готов указатель с номерами страниц

ed2k: ed2k stats

Год издания: 1966

Количество страниц: 272

Добавлена в каталог: 16.11.2005

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID

Предметный указатель

$(p, \mu)$ -последовательность      241
$P_{h}$ -таблица      90—92 259—262
$s_{v+1}$ -подтаблица      34
-таблица      222—226
-функции минимизация      222—226
-функция минимальная      222
$z_{v}$ -подтаблица      34
$\xi_{i}$ -совместимое состояние      177 178
k-различимость      79—82
k-эквивалентное разбиение      82—86
k-эквивалентность      79—82
x-память      215
z-память      215
Автоматы      см. «Конечные автоматы»
Алфавит входной      17
Алфавит выходной      17
Асинхронная система      15
Безусловные эксперименты      123
Вход-выход, последовательность      216
Входной алфавит      17
Входной символ      18
Входные переменные      14
Выходная последовательность      29
Выходной алфавит      17
Выходной символ      18
Выходные переменные      14
Граф переходов      40—43
Группировка      251
Группировка правильная      252
Группировка правильная минимальная      254
Дерево диагностическое      138—142
Дерево кратного эксперимента      153—155
Дерево преемников      135—138
Дерево установочное      161—164
Детерминированный конечный автомат      22
Диагностическая последовательность      127 141 142
Диагностический путь      141
Диагностическое дерево      138—142
Дискретность во времени      15 17
Достижимость      46 47
Дуга заходящая      43 53
Дуга исходящая      43 53
Зависимые переменные      24
Заходящая дуга      43 53
Избыточный путь      59
Изолированное состояние      43 53
Изолированный подавтомат      44 54 55
Изоморфные конечные автоматы      38 39 42 43
Импульсная характеристика линейного двоичного автомата      235 236
Исключительный класс      188
Источник синхронизирующий      15
Исходящая дуга      43 53
Квазиэквивалентность      251—254
Класс k-эквивалентности      82
Класс эквивалентности      87
Класс эквивалентных автоматов      102
Компактная $(p, \mu)$ -последовательность      241 242
Конечность алфавита      17—19
Конечные автоматы      21
Конечные автоматы (n,p,q)      37
Конечные автоматы (n,p,q) явно минимальные      37—40 116 117
Конечные автоматы (n,p,q) явно сократимые      37 38 39 116
Конечные автоматы без ограничений на входе      22
Конечные автоматы без потери информации      201—207
Конечные автоматы в покое      227
Конечные автоматы детерминированные      22
Конечные автоматы изоморфные      38 39 42 43
Конечные автоматы линейные двоичные      227—240
Конечные автоматы минимальные      110 111 116 117
Конечные автоматы нетривиальные      22
Конечные автоматы обратимые      198
Конечные автоматы различимые      100
Конечные автоматы разложимые      48
Конечные автоматы расщепляемые      49—51
Конечные автоматы с конечной памятью      210—222
Конечные автоматы с ограничениями на входе      49
Конечные автоматы сильносвязные      196—201 240
Конечные автоматы сравнимые      49
Конечные автоматы тривиальные      22
Конечные автоматы эквивалентные      100
Конечные автоматы эквивалентные, класс      102
Конечные автоматы, другая модель      27—29
Конечные автоматы, не зависящие от выхода      240—243
Конечные автоматы, основная модель      21 22
Конечные автоматы, примеры      22—24
Контур полный      63 64
Контур элементарный      58
Кратного эксперимента дерево      153—155
Кратные эксперименты      124
Линейные двоичные конечные автоматы      227—240
Линейные двоичные конечные автоматы, выходная последовательность периодическая      232
Линейные двоичные конечные автоматы, выходная последовательность свободная      232
Линейные двоичные конечные автоматы, импульсная характеристика      235 236
Максимальная память      215
Максимальное разложение автомата      48
Матрица переходов      52—55
Матрица переходов высшего порядка      55—58
Матрица переходов, частичное построение      68 69
Матрица переходов, эквивалентное разбиение      97—100
Матрица скелетная      65—67
Матрица совместимости      256
Минимальная x-z-таблица      226
Минимальная x-z-функция      222
Минимальная группировка      251 254
Минимальная форма      106—113 253
Минимальные конечные автоматы      110 111 116 117
Минимальный путь      61 62
Минимизация x-z-функции      222—226
Минимизация автомата      106—110 254—259
Множество совместимое      254
Множество состояний      19 24—27
Множество состояний допустимых начальных      126
Модифицированная скелетная матрица      67 62
Начальное состояние      30
Несовместимость      248
Нетривиальные конечные автоматы      22
Обратимые конечные автоматы      198
Общая задача распознавания автоматов      184—201
Объединение эквивалентных состояний      113—116
Ограничение на входе      248
Оператор задержки      229
Определение множества состояний по внутренней структуре      24—27
Определение памяти      220 222
Основное состояние      227
Память      215
Память x      215
Память z      215
Память максимальная      215
Память, определение      215

Пара «вход-выход»      41
Передаточное отношение      230
Переменные входные      14
Переменные выходные      14
Переменные зависимые      24
Переменные промежуточные      14
Перечисление автоматов      37—38
Период свободной выходной последовательности      232
Периодическая выходная последовательность линейного двоичного автомата      232
Петля      43 53
Повреждения, распознавание      192—196
Подавтомат      44
Подавтомат изолированный      45 54 55
Подавтомат преходящий      45 54 55
Подавтомат тупиковый      45 54 55
Подтаблица $s_{v+1}$       34
Подтаблица $z_{v}$       34
Полный контур      63 64
Последовательность $(p, \mu)$       241
Последовательность входная      29
Последовательность выходная      29
Последовательность установочная      163
Последовательность установочная минимальная      163
Последовательность «вход-выход»      216
Предсказание поведения автомата      29—31
Преходящее состояние      43 53
Преходящий подавтомат      45 54 55
Промежуточные переменные      14
Простые эксперименты      124
Путь      55
Путь диагностический      141
Путь избыточный      59
Путь минимальный      61 62
Путь установочный      163
Путь элементарный      58
Различимость автоматов      100—102
Различимость состояний      76—79
Различимость явная      77 78
Разложение автоматов      47—55
Разложение автоматов максимальное      48 49
Разложимые конечные автоматы      48
Разобщенное состояние      82
Распознавание повреждений      192—196
Распознающие эксперименты      см. «Эксперименты»
Расщепляемые конечные автоматы      49—51
Свободная выходная последовательность линейного двоичного автомата      232
Семейство перестановок      38—43
Сильносвязные конечные автоматы      196—201 240
Символ входной      18
Символ выходной      18
Синхронизирующий источник      15
Синхронизирующий сигнал      15
Система асинхронная      15
Система с конечной памятью      211—215
Система синхронная      15
Скелетная матрица      65—67
Скелетная матрица модифицированная      67 68
Совместимое множество      254
Совместимость      248—251
Совместимость, матрица      256
Сокращенная форма      113—116 253
Состояние      19—21
Состояние $\xi_{i}$ -совместимое      177 178
Состояние допустимое начальное      126
Состояние изолированное      43 53
Состояние начальное      30
Состояние основное      227
Состояние преходящее      43 53
Состояние разобщенное      82
Состояние с потерей информации      202
Состояние смежное      82
Состояние тупиковое      43 53
Состояние, класс эквивалентности      87
Состояние, различимость      76—79
Состояние, эквивалентное разбиение      87—100
Сравнимые конечные автоматы      49
Таблица x-z      222—226
Таблица минимальная x-z      226
Таблица пар      92—97 250 251
Таблица переходов      34—36
Таблица проверки потерь      204—206
Таблица эквивалентности      103—105
Тривиальные конечные автоматы      22
Тупиковое состояние      43 53
Тупиковый подавтомат      45 54 55
Уменьшение числа состояний автомата      113—116 259—263
Установочная последовательность      163
Установочное дерево      161—164
Установочный путь      163
Характеристика      см. «Линейные двоичные конечные автоматы»
Характеристические функции      22
Частичное построение матриц      68 69
Черный ящик      13 14 18
Эквивалентное разбиение автоматов      102—106
Эквивалентное разбиение матрицы переходов      97—100
Эквивалентное разбиение состояний      87—100
Эквивалентность автоматов      100—102
Эквивалентность состояний      75—79
Эквивалентность явная      77 78
Эквивалентность, класс      87
Эквивалентность, таблица      103—106
Эквивалентные автоматы      100
Эквивалентные автоматы, класс      102
Эквивалентных автоматов класс      102
Эксперименты безусловные      123
Эксперименты диагностические      125
Эксперименты диагностические для m состояний      126
Эксперименты диагностические для двух состояний      126—135
Эксперименты диагностические кратные безусловные      151—158 176
Эксперименты диагностические кратные условные      159—161 176
Эксперименты диагностические простые безусловные      142—145 176
Эксперименты диагностические простые условные      145—151 176
Эксперименты кратные      124
Эксперименты по распознаванию автоматов      184—201
Эксперименты по распознаванию автоматов из известного класса      188-193
Эксперименты по распознаванию автоматов линейных двоичных      237—240
Эксперименты по распознаванию автоматов, не зависящих от выхода      243
Эксперименты по распознаванию сильносвязных (n,p,q)-автоматов      200 201
Эксперименты по распознаванию состояний      122—178
Эксперименты простые      124
Эксперименты распознавания повреждений      192—196
Эксперименты установочные      125
Эксперименты установочные простые безусловные      164 165
Эксперименты установочные простые условные      165—168
Эксперименты установочные регулярные      168
Эксперименты установочные регулярные безусловные      168—171 176
Эксперименты установочные регулярные условные      171—176
Элементарный контур      58
Элементарный путь      58

Реклама

© Электронная библиотека попечительского совета мехмата МГУ, 2004-2024

Электронная библиотека мехмата МГУ

Valid HTML 4.01!

|

Valid CSS!

О проекте