АВТОМАТОВ ТЕОРИЯ
часть теоретич. кибернетики, объектом исследования к-рой
являются различные преобразователи дискретной информации; возникла в нач.
50-х гг. 20 в. в связи с требованиями практики проектирования вычислит,
машин и с разработкой математич. моделей процессов переработки информации
в биол., экономич. и др. системах. А.т.- самостоятельный раздел математики,
имеющий разнообразную проблематику и приложения.
Осн. понятиями
А. т. являются понятия абстрактного автомата и понятие композиции автоматов.
Эти понятия являются разумными абстракциями реально существующих дискретных
устройств - автоматов. Понятие абстрактного автомата позволяет характеризовать
устройство с точки зрения алгоритма его функционирования, т. е.
алгоритма переработки информации, к-рый оно реализует. Понятие композиции
автоматов позволяет характеризовать устройство с точки зрения его структуры,
иными словами, даёт представление, каким образом данное устройство построено
из других, более элементарных.
А. т. состоит
из ряда разделов. Один из разделов: абстрактно-алгебраическая А. т. В этом
разделе абстрактные автоматы изучаются с точки зрения исследования их свойств
и различных способов задания. Абстрактным автоматом наз. объект А =А
(Я,
X,Y,S,X), состоящий из трёх непустых множеств: Я - состояний, X - входных
сигналов, Y - выходных сигналов, и двух функций, осуществляющих однозначное
отображение множества Я X X в Я, 6 (а, х) переходов и множества
ЯХХвУ, X. (а, х) выходов. Абстрактный автомат наз. конечным, если
множества 51, X, Y-конечны. В абстракт-но-алгебр. А. т. можно выделить
теорию конечных автоматов и теорию бесконечных автоматов. Осн. вопросы
теории конечных автоматов можно считать решёнными. Наиболее интересными
результатами теории конечных автоматов являются: теорема анализа и синтеза
конечных автоматов, к-рая даёт характеристику событий, представленных в
конечных автоматах, теоремы об определяющих соотношениях в алгебре регулярных
событий, оценки длины экспериментов с конечными автоматами, а также ряд
результатов по исследованию алгебр, свойств абстрактных автоматов. В теории
бесконечных автоматов рассматриваются различные концепции бесконечных автоматов,
точнее выделяются классы бесконечных автоматов специального вида. Этот
раздел важен тесной связью с общей теорией формальных языков и грамматик
(см. Математическая лингвистика), а также с теорией алгоритмов (см.
Алгоритмов
теория). В рамках абстрактно-алгебр. А. т. наметился (конец 60-х гг.)
подход к решению проблемы создания алгебры алгоритмов и построения аппарата
для формальных преобразований выражений в этой алгебре, что позволяет совершенно
по-новому подойти к решению такого рода задач, как эквивалентность схем
алгоритмов, и даёт возможность эффективно решать оптимизационные задачи
в проектировании дискретных устройств.
Другим разделом
А. т. является структурная А. т. Здесь автомат представляется в виде сети,
элементы к-рой выбираются из нек-рой заданной совокупности элементарных
автоматов, соединены между собой нек-рым специальным образом и осуществляют
запоминание и преобразование элементарных сигналов. Осн. результатами структурной
А. т. являются: практич. методика построения сложных логич. сетей, исследования
по асимптотич. оценкам сложности их, решению проблемы полноты системы элементарных
автоматов, кодированию состояний автоматов, оптимальной реализации логич.
сетей в различных элементных структурах и т. д. Структурная А. т. тесно
связана с теорией кодирования, общей теорией переключательных функций,
теорией комбинационных схем, теорией информации, теорией надёжности дискретных
устройств и т. п.
Третьим разделом
А. т. является теория вероятностных автоматов и самоорганизующихся систем.
Осн. приложения
А. т. имеет в практике проектирования и автоматизации проектирования дискретных
устройств и, в частности, вычислит, машин. Она приобретает всё более важное
значение для таких классич. математич. дисциплин, как теория алгоритмов,
с одной стороны, и таких совр. теорий в математике и кибернетике, как теория
формальных систем, теория программирования, теория формальных языков и
грамматик - с другой.
Лит.: Автоматы.
Сб. ст., под ред. К. Э. Шеннона и Дж. Маккарти, пер. с англ., М., 1956;
Глушков В. М., Синтез цифровых автоматов, М., 1962; его же, Введение в
кибернетику, К., 1964; Кобринский Н. Е., Трахтенброт Б. А., Введение в
теори ю конечных автоматов, М., 1962; Логика. Автоматы. Алгоритмы, М.,
1963; Гилл А., Введение в теорию конечных автоматов, пер. с англ., М.,
1966. Ю.В.Капитонова.
А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я