Конечные автоматы

Конечный автомат- автомат, у которого множество состояний, а также множество входных и выходных сигналов являются конечными. Конечный автомат может быть моделью технического устройства (ЭВМ, релейное устройство) важными направлениями теории конечных автоматов (помимо традиционных задач и синтеза автоматических систем управления), имеющими большое практическое значение, являются синтез надежных элементов из ненадежных компонентов и исследование поведения конечных автоматов в случайных средах.

Конечный автомат — абстрактный автомат без выходного потока, число возможных состояний которого конечно. Результат работы автомата определяется по его конечному состоянию.

Существуют различные варианты задания конечного автомата. Например, конечный автомат может быть задан с помощью пяти параметров: , где:

• Q — конечное множество состояний автомата;
• q₀ — начальное (стартовое) состояние автомата ();
• F — множество заключительных (или допускающих) состояний, таких что ;
• Σ — допустимый входной алфавит (конечное множество допустимых входных символов), из которого формируются строки, считываемые автоматом;
• δ — заданное отображение множества во множество подмножеств Q:

(иногда δ называют функцией переходов автомата).

Автомат начинает работу в состоянии q₀, считывая по одному символу входной строки. Считанный символ переводит автомат в новое состояние из Q в соответствии с функцией переходов. Если по завершении считывания входного слова (цепочки символов) автомат оказывается в одном из допускающих состояний, то слово «принимается» автоматом. В этом случае говорят, что оно принадлежит языку данного автомата. В противном случае слово «отвергается».

Конечные автоматы широко используются на практике, например в синтаксических, лексических анализаторах, и тестировании программного обеспечения на основе моделей.