Теория автоматов — раздел дискретной математики, изучающий абстрактные автоматы — вычислительные машины, представленные в виде математических моделей — и задачи, которые они могут решать.
Теория автоматов наиболее тесно связана с теорией алгоритмов: автомат преобразует дискретную информацию по шагам в дискретные моменты времени и формирует результат по шагам заданного алгоритма.
Существует алгебраическая трактовка теории автоматов, использующая полукольца, формальные степенные ряды, формальные ряды над деревьями, теорию неподвижных точек и теорию матриц[1].
Символ — любой атомарный (то есть неделимый более без потери смысла) блок данных, который может производить эффект на машину. Чаще всего символ — это буква некоего формального языка. Например, символы, применяемые во многих языках программирования, включают буквы обычного языка, разделители, также какие-то дополнительные знаки. Но символом может быть, к примеру, ключевое слово целиком некоего языка программирования (if, for, while и т. д.), графический элемент диаграммы и т. д.
В теории автоматов под этим словом понимается формальная (математическая) конструкция, которая задаёт алгоритм,назначением которого является определение принадлежности заданного слова входному языку, описываемому данным формальным автоматом. Слово «формальный» подчёркивает отличие такого автомата от воплощённых в металле станков-автоматов, автоматических коробок передач и иных подобных устройств. Для краткости изложения в соответствующих пособиях прилагательное «формальный» или «математический» часто опускается (начиная с названия теории — точнее было бы «теория формальных автоматов»), когда понятно о чём идёт речь.
Для выполнения своего назначения все (формальные) автоматы наделяются свойством нахождения в некотором допустимом состоянии и функциями переходов автомата, в простейшем случае (конечные автоматы) задающих только возможность перехода из одного состояние в другое при чтении очередного символа из входной цепочки. После очередного перехода читающая головка автомата сдвигается на один символ (он «прочитывается»). Так происходит пока не достигнут конец читаемого слова, либо не найдена подходящая функция перехода.