Читать онлайн «Введение в теорию автоматов»

В. Б. КУДРЯВЦЕВ СВ. АЛЕШИН А. С. ПОДКОЛЗИН ВВЕДЕНИЕ В ТЕОРИЮ АВТОМАТОВ МОСКВА "НАУКА" ГЛАВНАЯ РЕДАКЦИЯ ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ 1985 6БК 22. 18 K88 УДК 519. 71 Кудрявцев В. Б. , Алешин СВ. , Подколзии А. С Введение в теорию автоматов — М. : Наука. Гл. ред. физ. -мат. лит. , 1985. - 320 с. Содержит изложение основ теории автоматов, представляющих собой одну из основных моделей управляющих систем. Достаточно широко представлены результаты по теории абстрактных и структурных автоматов, полученные отечественными и зарубежными авторами за последние 30 лет, т. е. за время с момента возникновения и последующего формирования теории автоматов. Для специалистов, работающих в области математической кибернетики и дискретной математики, а также для учащихся вузов, специализирующихся в этих областях; она будет полезна также инженерам, желающим углубить свои знания в кибернетике. Ил. 163. Библиогр. 87 назв. Рецензент доктор технических наук, профессор А. М- Богомолов 1702070000-158 ■—■ ">П RS 053 (02)-85 ©Издательство "Наука", Главная редакция физико-математической литературы, 1985 ОГЛАВЛЕНИЕ Введение 5 Глава 1. Понятие автомата 8 § 1. Понятие конечного автомата -. 8 -~§ 2. -Обобщения понятия конечного автомата. . . ". ,,-. -"31 Глава 2. Абстрактные автоматы. . 39 § 1. Ограниченно-детерминированные функции 39 § 2. Эквивалентность конечных автоматов '. 44 § 3. г-неотличимость конечных автоматов 50 § 4. Отличимость состояний конечных автоматов 57 & 5. Кратные эксперименты с конечными автоматами 63 § 6. Простые эксперименты с конечными автоматами 80 § 7. Конечные автоматы как акцепторы 91 § 8. Конечные автоматы как сверхакцепторы 100 § 9. Конечные автоматы как перечислители 108 § 10. Взаимодействие конечных автоматов и конечные автоматы в лабиринтах 116 § 11. Оценка числа автоматов приведенного вида. . . . 130 § 12. Конечные автоматы как числовые акцепторы и преобразователи 137 Глава 3. Структурные автоматы 151 § 1. Ограниченно-детерминированные функции многих переменных 151 § 2. Канонические уравнения 152 § 3. Операции над ограниченно-детерминированными функциями 155 § 4. Схемы. Структурный автомат 161 § 5. Замыкание. Выразимость. Задача о полноте 154 § 6. Конечные /f-полные системы ' 167 § 7. 2-полнота 174 § 8. Л-замыкание . . ■ 179 § 9. Предполные классы 183 § 10. Алгоритмическая неразрешимость задач о К- и Л-полноте . 190 §11. Разрешимый случай задачи о полноте. Линейные автоматы . 195 § 12. Ограниченно-детерминированные функции одной переменной 224 § 13. Группа/lSj 229 1* 3 § 14. Гомоморфизм автоматов. Моделирование 236 §15. Задача о выразимости для детерминированных функций 247 Глава 4. Однородные структуры 253 § 1. Определения и примеры 253 § 2. Графы переходов однородных структур 265 § 3. Анализ поведений однородных структур 274 | 4. Моделирование в однородных структурах 295 Список литературы 311 Предметный указатель •. ■ 314 Именной указатель 317 Список обозначений 318 ВВЕДЕНИЕ Теория автоматов представляет собой раздел теории управляющих систем [64], изучающий математические модели преобразователей дискретной информации, называемые автоматами.