Автоматов теория

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

Е. Алгоритма переработки информации, который оно реализует. Понятие композиции автоматов позволяет характеризовать устройство с точки зрения его структуры, иными словами, даёт представление, каким образом данное устройство построено из других, более элементарных. А. Т. Состоит из ряда разделов. Один из разделов. Абстрактно-алгебраическая А. Т. В этом разделе абстрактные автоматы изучаются с точки зрения исследования их свойств и различных способов задания. Абстрактным автоматом называют объект А = А (U, X, Y, δ, λ), состоящий из трёх непустых множеств. U — состояний, Х — входных сигналов, Y — выходных сигналов, и двух функций, осуществляющих однозначное отображение множества U×Х в U, δ (а, х) переходов и множества U×Х в Y, λ (а, x) выходов.

Абстрактный автомат называется конечным, если множества U, X, Y — конечны. В абстрактно-алгебраической А. Т. Можно выделить теорию конечных автоматов и теорию бесконечных автоматов. Основные вопросы теории конечных автоматов можно считать решенными. Наиболее интересными результатами теории конечных автоматов являются. Теорема анализа и синтеза конечных автоматов, которая даёт характеристику событий, представленных в конечных автоматах, теоремы об определяющих соотношениях в алгебре регулярных событий, оценки длины экспериментов с конечными автоматами, а также ряд результатов по исследованию алгебраических свойств абстрактных автоматов. В теории бесконечных автоматов рассматриваются различные концепции бесконечных автоматов, точнее выделяются классы бесконечных автоматов специального вида.

Этот раздел важен тесной связью с общей теорией формальных языков и грамматик (см. Математическая лингвистика), а также с теорией алгоритмов (см. Алгоритмов теория). В рамках абстрактно-алгебраической А. Т. Наметился (конец 60-х гг.) подход к решению проблемы создания алгебры алгоритмов и построения аппарата для формальных преобразований выражений в этой алгебре, что позволяет совершенно по-новому подойти к решению такого рода задач, как эквивалентность схем алгоритмов, и даёт возможность эффективно решать оптимизационные задачи в проектировании дискретных устройств. Другим разделом А. Т. Является структурная А. Т. Здесь автомат представляется в виде сети, элементы которой выбираются из некоторой заданной совокупности элементарных автоматов, соединены между собой некоторым специальным образом и осуществляют запоминание и преобразование элементарных сигналов.

Основными результатами структурной А. Т. Являются. Практическая методика построения сложных логических сетей, исследования по асимптотическим оценкам сложности их, решению проблемы полноты системы элементарных автоматов, кодированию состояний автоматов, оптимальной реализации логических сетей в различных элементных структурах и т. Д. Структурная А. Т. Тесно связана с теорией кодирования, общей теорией переключательных функций, теорией комбинационных схем, теорией информации, теорией надёжности дискретных устройств и т. П. Третьим разделом А. Т. Является теория вероятностных автоматов и самоорганизующихся систем. Основные приложения А. Т. Имеет в практике проектирования и автоматизации проектирования дискретных устройств и, в частности, вычислительных машин.

Она приобретает всё более важное значение для таких классических математических дисциплин, как теория алгоритмов, с одной стороны, и таких современных теорий в математике и кибернетике, как теория формальных систем, теория программирования, теория формальных языков и грамматик — с другой. Лит. Автоматы. Сб. Ст., под ред. Э. Шеннона и Дж. Маккарти, пер. С англ., М., 1956. Глушков В. М, Трахтенброт Б. А, Введение в теорию конечных автоматов, М., 1962. Логика. Автоматы. Алгоритмы, М., 1963. Гилл А., Введение в теорию конечных автоматов, пер. С англ., М. 1966. Ю. В. Капитонова..