Читать онлайн «Введение в теорию абстрактных автоматов»

В. Б. Кудрявцев, А. С. Подколзин, Ш. Ушчумлич ВВЕДЕНИЕ В ТЕОРИЮ АБСТРАКТНЫХ АВТОМАТОВ Допущено Министерством высшего и среднего специального образования СССР в качестве учебного пособия для студентов университетов, обучающихся по специальности «Математика» ИЗДАТЕЛЬСТВО МОСКОВСКОГО УНИВЕРСИТЕТА 1985 УДК 519. 95 Кудрявцев В. Б. , Подколзин А. С, Ушчумлич Ш. Введение в теорию абстрактных автоматов. — М. . Изд-во Моск. ун-та, 1985. — 174 с. Теория автоматов представляет собой раздел теории управляю- щих систем, изучающий математические модели преобразователей дискретной информации, называемые автоматами, прототипами ко- торых являются различные реальные устройства. Предлагаемая кни- га содержит достаточно обширный материал по теории абстрактных автоматов и посвящена рассмотрению основных типов поведений автоматов, таких как автоматы-акцепторы, преобразователи, пере- числители и. т. п. , а также изучению возникающих здесь задач ана- лиза и синтеза автоматов, учитывающему их сложностной аспект. Рецензенты: кафедра математической кибернетики Саратовского государственного университета им Η. Γ Чернышевского, докт. физ. -матем. наук Ю. И. ЯНОВ 1502000000—142 © Издательство Московского 077(02)—85 ЙЬ й* университета, 1985 г. ОГЛАВЛЕНИЕ Введение 4 Глава I. Понятие автомата 6 § 1. Примеры и содержательная модель автомата 6 § 2. Понятие абстрактного автомата. Способы задания автоматов . 10 § 3. Некоторые классы абстрактных автоматов 15 § 4. Типы поведений автоматов. Анализ и синтез автоматов . . 20 § 5. Некоторые модификации абстрактных конечных автоматов . 27 Глава П. Автоматы как преобразователи 32 § 1. Ограниченно-детерминированные функции 32 § 2. Эквивалентность автоматов 38 § 3, Эксперименты с автоматами 48 § 4. Некоторые вспомогательные утверждения 56 § 5 Оценки сложности экспериментов для классов Ж Глава III. Автоматы как акцепторы 7$ § 1. Представление событий автоматами. Теорема' Клини ... 76 § 2. Алгоритмы анализа и синтеза автоматов · 85 § 3. Качественные характеристики основных алгоритмов анализа и синтеза автоматов 95 § 4. Метрические характеристики основных алгоритмов анализа ав- томатов 116 § 5. Эффективность основных алгоритмов анализа и синтеза ав- томатов 127 Глава IV. Некоторые другие виды поведений 140 § 1. Конечные автоматы как сверхакцепторы 140 § 2. Конечные автоматы как перечислители 147 § 3. Взаимодействие конечных автоматов и конечные автоматы в лабиринтах 157 Литература 173 ВВЕДЕНИЕ Теория автоматов представляет собой раздел теории управляю- щих систем, изучающий математические модели преобразователей дискретной информации, называемые автоматами. С определенной точки зрения такими преобразователями являются как реальные устройства (вычислительные машины, автоматы, живые организ- мы и т. п. ), так и абстрактные системы (математические машины, аксиоматические теории и т. д. ). Характерной особенностью этих преобразователей является дискретность функционирования и конечность областей значений параметров, описывающих их. Тео- рия автоматов возникла в середине XX столетия в связи с изуче- нием свойств конечных автоматов.