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

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

Авторизация

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

Брауэр В. — Введение в теорию конечных автоматов

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

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

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

Автор: Брауэр В.

Аннотация:

В книге профессора Гамбургского университета описаны основные классические модели теории конечных автоматов (автоматы Мили и Мура) и более сложные модели (автоматы Рабина — Скотта, многоленточные автоматы, конечные преобразователи). Рассмотрены преобразования конечных автоматов и регулярные множества. Существенную часть книги составляют упражнения.
Для инженерно-технических работников, связанных с приложениями теории конечных автоматов, а также работающих в области информатики и вычислительной техники.

Язык:

Рубрика: Computer science/Вычислимость/

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

ed2k: ed2k stats

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

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

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

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

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

0-доопределение      135
2-РС-автомат      352
2-ЭМ-автомат      328
2-ЭЭШ-автомат      336
a-преобразователь      314
a-преобразователь $\Lambda$ -свободный      315
a-преобразователь алфавитный      315
k-префикс      300
k-суффикс      62
l-эквивалентность      128
LW-последовательность      209
U-изоморфизм      133
U-реакция состояния частичного автомата Мили      127
U-реакция частичного автомата Мили      133
U-эквивалентность      128
U-эпиморфизм      133
uvw-теорема      192
V-эквивалентность      128
Z-гомоморфизм      85
ZXY-гомоморфизм      85
Автомат двуленточный Рабина — Скотта (2-РС-автомат)      352
Автомат двуленточный Эйленберга — Элго — Шефердсона (2-ЭЭШ-автомат)      336
Автомат двуленточный Элго — Мезея (2-ЭМ-автомат)      328
Автомат двусторонний      290
Автомат зеркальный      178
Автомат Мили      36
Автомат Мили k-финально различающий входы      62
Автомат Мили без потери информации      58
Автомат Мили входно-независимый      75
Автомат Мили различающий входы      58
Автомат Мили с конечной памятью      64
Автомат Мили сокращенный      38
Автомат Мили частичный      125
Автомат Мили частичный U-минимальный      133
Автомат Мили частичный U-сокращенный      133
Автомат многоленточный      358
Автомат Мура      74
Автомат Мура инициальный      115
Автомат Мура минимальный      88
Автомат Мура сильно связный      114
Автомат Мура сокращенный      77
Автомат Мура сокращенный по Мили      113
Автомат недетерминированный (НРС-автомат)      169
Автомат Рабина детерминированный (ДРС-автомат)      185
Автомат Рабина — Скотта (РС-автомат)      186
Автомат с предварительным просмотром      299
Автомат с предварительным просмотром k-детерминированный      300
Автомат с предварительным просмотром многозначный      299
Автомат с предварительным просмотром однозначный      299
Автомат Уоляспера (У-автомат)      360
Аксиом система (для рациональных равенств)      218
Алгебра булева      12
Алгебра Клини      216
Алфавит      28
Аппроксимация      89
Биекция      16
Булеан      11
Вершина      18
Вход      36
Выражение рациональное      213
Выражение рациональное обобщенное      268 273
Выражение рациональное эквационально определимое      230
Выражение рациональное, левое производное      265
Выход      36
Гомоморфизм      25
Гомоморфизм $\Lambda$ -свободный      28
Гомоморфизм автоматов      85
Гомоморфизм алфавитный      28
Грамматика линейная      335
Грамматика праволинейная      174
Грань      21
Граф      18
Граф Майхилла      279
Граф Майхилла $\Lambda$ -свободный      279
Граф Майхилла взвешенный      279
График      14
Группа      24
Диагональ (декартова произведения)      13
Диаграмма      17
Доопределение (автомата)      135
ДРС-автомат      185
Закон ассоциативности      12
Закон дистрибутивности      12
Закон идемпотентности      11
Закон коммутативности      22
Закон Моргана      12
Закон поглощения      12
Замкнутость (относительно булевых операций)      11
Замыкание относительно операций      21
Замыкание относительно отношений      21
Изоморфизм      26
Изоморфизм автоматов Мура      85
Изоморфизм НРС-автоматов      244
Инъекция      16
Класс эквивалентности      22
Композиция (суперпозиция)      15
Конгруэнция (отношение конгруэнтности)      26
Конгруэнция порожденная отношением      27
Конгруэнция синтаксическая      187
Конкатенация      28
Конфигурация      290
Маркировка      369
Маршрут (путь)      19
Матрица переходно-выходная      36
Матрица смежности      19
Множество Д-допустимое      186
Множество допустимое      186
Множество конечно-периодическое      305
Множество кусочно-тестируемое      227
Множество локально тестируемое      226
Множество локальное      285
Множество маршрутное      279
Множество маршрутное взвешенное      279
Множество Медведева — Костича      287
Множество Н-допустимое      176
Множество однозначное рациональное      226
Множество порождающее      27
Множество порождающее свободное      27
Множество псевдорациональное      308
Множество различимое      187
Множество рациональное      176
Множество регулярное      176
Множество стандартное      285
Множество упорядоченное      21
Моноид      23
Моноид переходов      171
Моноид свободно порожденный      27
Моноид синтаксический      188
Моноид слов      28
НРС-автомат      169
НРС-автомат D-минимальный      244
НРС-автомат N-минимальный      244
НРС-автомат алфавитный      169
НРС-автомат избыточный      237
НРС-автомат инициально связный      237
НРС-автомат побуквенный      169
НРС-автомат сокращенный      243
НРС-автомат экспоненциальный      241
Образ множества      15
Образ элемента      15
Объединение множеств      12
Объединение соответствий      15
Ограничение (сужение) отображения      15
Оператор замыкания      149
Оператор замыкания аддитивный      149
Операция булева      10
Операция образования подмоноида      177
Операция рациональная      177
Орграф      19
Орграф взвешенный      19

Отношение      18
Отношение антисимметричное      20
Отношение конгруэнтности (конгруэнция)      26
Отношение линейного порядка      20
Отношение нулевое      18
Отношение последовательностное      68
Отношение рациональное      334
Отношение рефлексивное      20
Отношение симметричное      20
Отношение тождественно истинное      18
Отношение транзитивное      20
Отношение частичного порядка      20
Отношение эквивалентности      20
Отображение (функция)      15
Отображение a-преобразовательное      315
Отображение автоматное      67
Отображение биективное (биекция)      16
Отображение всюду определенное (тотальное)      15
Отображение инъективное (инъекция)      16
Отображение Мр-представимое      89
Отображение полное      89
Отображение последовательностное      89
Отображение сохраняющее длину слов      89
Отображение сюръективное (сюръекция)      16
Отображение тотальное (всюду определенное)      15
Отображение частичное      15
Память автомата Мили      64
Поведение состояния автомата      127
Подавтомат      126
Подавтомат релевантный      133
Подвыражение правильное      215
Подмоноид      23
Подмоноид порожденный      177
Подполугруппа      23
Подполугруппа порожденная      27
Полугруппа      23
Полугруппа свободная      27
Полугруппа свободно порожденная      27
Полукольцо      25
Последовательность конечно-периодическая      309
Последовательность символов (слово)      27
Правило замены      218
Правило решения уравнений      218
Преобразование порожденное a-преобразователем      315
Преобразование рациональное      315
Преобразование частичных автоматов Мили      140
Преобразование частичных автоматов Мили каноническое      141
Преобразование частичных автоматов Мили однозначное      140
Преобразование, определенное автоматом Мили      68
Преобразователь конечный      313
Проблема соответствий Поста      326
Проблема соответствий Поста ослабленная      368
Продолжение (расширение) отображения      15
Проекция      17
Произведение декартово множеств      13
Произведение декартово соответствий      15
Произведение прямое моноидов      332
Прообраз множества      15
Прообраз элемента      15
Путь (маршрут)      19
Равенство рациональное      213
Равенство соответствий      15
Равносильность 2-ЭМ-автоматов и a-преобразователей      329
Равносильность автоматов Мили и Мура      79
Равносильность автоматов Мура      79
Равносильность двусторонних и РС-автоматов      294
Равносильность состояний автоматов Мура      113
Различимость автоматов Мура      116
Различимость автоматов Мура сильная      116
Различимость входных последовательностей      58
Разность множеств      11
Разность множеств симметрическая      11
Расширение (продолжение) отображения      15
Реакция 2-РС-автомата      352
Реакция 2-ЭМ-автомата      328
Реакция автомата двустороннего      290
Реакция автомата Мили      38
Реакция автомата Мура      77
Реакция множества состояний НРС-автомата      243
Реакция НРС-автомата      176
Реакция НРС-автомата локальная      261
Реакция состояния автомата Мили      38
Реакция состояния автомата Мура      77
Реакция состояния частичного автомата Мили      127
Реакция У-автомата      360
Ребро      18
Релевантность состояния      133
Решетка      22
РС-автомат      186
Свойство пустого слова для матриц      209
Свойство пустого слова для рациональных выражений      217
Следствие Берстела      320
Следствие Пратера      151
Следствие Ритчи      197
Слово (последовательность символов)      27
Слово зеркальное      115 171
Слово пустое      38
Совместность состояний      130
Соответствие      14
Соответствие обратное      14
Соответствие переходов 2-ЭМ-автомата      328
Соответствие переходов НРС-автомата      169
Соответствие последовательностное      170 315
Соответствие функционирования      314
Соответствие функционирования последовательностное      315
Состояние достижимое      237
Состояние избыточное      237
Состояние поглощающее      237
Состояние релевантное      133
Сужение (ограничение)      15
Суперпозиция (композиция)      15
Сходство рациональных выражений      272
Теорема Ардена      208
Теорема Ардена — Боднарчука      209
Теорема Бжозовского — Спивака      267
Теорема Гилла      64
Теорема Гинзбурга      131
Теорема Грасселли — Лючио      152
Теорема Гриффитса      322
Теорема Индермарка — Камеды — Вайнера      261
Теорема Карпа (об аппроксимации)      90
Теорема Клини      178 180
Теорема Клини — Майхилла      195
Теорема Леви      29
Теорема Майхилла (о допустимых и различимых множествах)      188
Теорема Майхилла (о стандартных множествах)      286
Теорема Медведева — Костича      287
Теорема Мура (о неопределенности)      78
Теорема Мюнтеферинга (о преобразованиях)      140
Теорема Нивата      317
Теорема о гомоморфизмах      26
Теорема о графах Майхилла      283
Теорема о итеративном подслове      191
Теорема о моноиде переходов      171
Теорема о однозначности минимального PC-автомата      248
Теорема о периодичности      62
Теорема о разложении отображений      22
Теорема о сокращении автоматов Мили      41
Теорема о сокращении автоматов Мура      77
Теорема о сокращении частичных автоматов Мили      136
Теорема Полла, Унгера      150
Теорема Рабина — Скотта (о НРС- и РС-автоматах)      195
Теорема Рабина — Скотта (об экспоненциальном автомате)      241
Теорема Саломаа — Урпонена      219
Теорема Уоляспера      361
Теорема Урпонена      221
Теорема Хаффмана — Мили      39
Теорема Хиббарда      110
Теорема Хомского — Шютценбергера      285
Теорема Чена      60

1 2

О проекте