Категория:Теория автоматов

В дискретной математике, разделе информатики, теория автоматов (automata theory) изучает абстрактные машины в виде математических моделей, и проблемы, которые они могут решать.

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

При анализе автоматов изучают их поведение при различных возмущающих воздействиях и минимизируют число состояний автомата для работы по заданному алгоритму. Такой автомат называют абстрактным. При синтезе автоматов формируют систему из элементарных автоматов, эквивалентную заданному абстрактному автомату. Такой автомат называется структурным.

Автоматы часто классифицируются через формальные языки, которые они могут распознавать.

Теория автоматов применяется при разработке лексических и синтаксических анализаторов трансляторов. Другое важнейшее применение теории автоматов --- математически строгое нахождение разрешимости и сложности проблем.

Есть несколько классов автоматов, например конечные автоматы (различают детерминированные и недетерминированные конечные автоматы), МП-автоматы, ЛО-автоматы, клеточные автоматы (игра «жизнь»), машины Тьюринга.