Автоматів теорія, частина теоретичною кібернетики, об'єктом дослідження якої є різні перетворювачі дискретної інформації; виникла на початку 50-х рр. 20 ст у зв'язку з вимогами практики проектування обчислювальних машин і з розробкою математичних моделей процесів переробки інформації в біологічних, економічних і інших системах. А. т. — самостійний розділ математики, що має всіляку проблематику і додатки.
Основними поняттями А. т. є поняття абстрактного автомата і поняття композиції автоматів. Ці поняття є розумними абстракціями реально існуючих дискретних пристроїв — автоматів . Поняття абстрактного автомата дозволяє характеризувати пристрій з точки зору алгоритму його функціонування, тобто алгоритму переробки інформації, який воно реалізує. Поняття композиції автоматів дозволяє характеризувати пристрій з точки зору його структури, іншими словами, дає виставу, яким чином даний пристрій побудований з інших, більш елементарних.
А. т. складається з ряду розділів. Один з розділів: абстрактна алгебра А. т. У цьому розділі абстрактні автомати вивчаються з точки зору дослідження їх властивостей і різних способів завдання. Абстрактним автоматом називають об'єкт А = А, що складається з трьох непорожньої безлічі: U — станів, Х — вхідних сигналів, Y — вихідних сигналів, і двох функцій, що здійснюють однозначне відображення безлічі U´Х у U, d ( а, х ) переходів і безлічі U´Х у Y, l ( а, x ) виходів. Абстрактний автомат називається кінцевим, якщо безліч U, X, Y — кінцеві. У абстрактною алгеброю А. т. можна виділити теорію кінцевих автоматів і теорію безконечних автоматів. Основні питання теорії кінцевих автоматів можна вважати вирішеними. Найцікавішими результатами теорії кінцевих автоматів є: теорема аналізу і синтезу кінцевих автоматів, яка дає характеристику подій, представлених в кінцевих автоматах, теореми про визначальні співвідношення в алгебрі регулярних подій, оцінки довжини експериментів з кінцевими автоматами, а також ряд результатів по дослідженню властивостей алгебри абстрактних автоматів. У теорії безконечних автоматів розглядаються різні концепції безконечних автоматів, точніше виділяються класи безконечних автоматів спеціального вигляду. Цей розділ важливий тісним зв'язком із загальною теорією формальних мов і граматик (див. Математична лінгвістика ), а також з теорією алгоритмів (див. Алгоритмів теорія ). В рамках абстрактної алгебри А. т. намітився (кінець 60-х рр.) підхід до рішення проблеми створення алгебри алгоритмів і побудови апарату для формальних перетворень виразів в цій алгебрі, що дозволяє абсолютно по-новому підійти до вирішення такого роду завдань, як еквівалентність схем алгоритмів, і дає можливість ефективно вирішувати оптимізаційні завдання в проектуванні дискретних пристроїв.
Іншим розділом А. т. є структурна А. т. Тут автомат представляється у вигляді мережі, елементи якої вибираються з деякої заданої сукупності елементарних автоматів, сполучені між собою деяким спеціальним чином і здійснюють запам'ятовування і перетворення елементарних сигналів. Основними результатами структурної А. т. є: практична методика побудови складних логічних мереж, дослідження по асимптотичним оцінкам складності їх, вирішенню проблеми повноти системи елементарних автоматів, кодуванню станів автоматів, оптимальній реалізації логічних мереж в різних елементних структурах і так далі Структурна А. т. тісно пов'язана з теорією кодування, загальною теорією функцій перемикачів, теорією комбінаційних схем, теорією інформації, теорією надійності дискретних пристроїв і тому подібне
Третім розділом А. т. є теорія імовірнісних автоматів і систем, що самоорганізующихся.
Основні застосування А. т. має в практиці проектування і автоматизації проектування дискретних пристроїв і, зокрема, обчислювальних машин. Вона набуває усе більш важливого значення для таких класичних математичних дисциплін, як теорія алгоритмів, з одного боку, і таких сучасних теорій в математиці і кібернетиці, як теорія формальних систем, теорія програмування, теорія формальних мов і граматик — з іншою.
Літ.: Автомати. Сб. ст., під ред. Е. Шеннона і Дж. Маккарті, пер.(переведення) з англ.(англійський), М., 1956; Глушков В. М, Трахтенброт Б. А, Введеніє в теорію кінцевих автоматів, М., 1962; Логіка. Автомати. Алгоритми, М., 1963; Гилл А., Введення в теорію кінцевих автоматів, пер.(переведення) з англ.(англійський), М. 1966.
