Моделирование потоков работ конечными автоматами
Теория автоматов — раздел теории управляющих систем, который изучает модели преобразователей дискретной информации, называемые автоматами. Теория конечных автоматов может быть с успехом использована для моделирования таких объектов, как вычислительные системы, технологические процессы, управляющие и организационные структуры.
В общем случае её применение позволяет вычислять, компактно представлять, анализировать и прогнозировать процессы в динамических системах при сложных входных воздействиях [19,20,21].Предпосылкой активного использования теории конечных автоматов для моделирования сложных объектов является наличие развитого математического аппарата. Если отвлечься от технических деталей, то можно прийти к понятию абстрактного конечного автомата.
Конечный автомат — это пятерка К = {(фН,фА,іД, где
Q — множество конечных состояний автомата;
А — алфавит автомата (конечное множество входных [/, выходных V и промежуточных символов или букв);
6 — функция переходов, она задаёт отображение вида S : Q х х А —> Q (переход из одного состояния в другое под воздействием символов входного алфавита);
А — функция выходов, её вид зависит от типа конечного автомата;
F — множество выделенных (распознанных) состояний. Данное множество является подмножеством множества Q.
Среди выделенных состояний могут быть, например, состояние ошибки или состояние нормального завершения процесса. Эти автоматы предназначены для решения задач, связанных, например, с разбором текста, распознаванием необходимой цепочки символов, анализом анкет, нахождением информации в базе данных и др. Под воздействием последовательности входных сигналов (букв алфавита А) конечный автомат переходит из одного состояния в другое и оказывается в конечном состоянии, принадлежащем Е, в случае распознания входной последовательности. Конечный автомат может быть представлен в виде графа, множество вершин которого соответствует множеству Q.
Рис. 2.7. Пример распознающего автомата
Рис. 2.8. Микропрограмма работы УА
Из вершины Qi в вершину Qj ведет дуга, помеченная символом алфавита, если есть соответствующая команда (буква алфавита), которая переводит автомат из состояния qi в состояние Qj. Последовательность букв интерпретируется при этом как входное слово. Множество допустимых слов образует язык автомата.
