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