Интернет магазин китайских планшетных компьютеров

Компьютеры - Конечный автомат

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

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

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

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

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