Моделирование потоков работ конечными автоматами

Теория автоматов — раздел теории управляющих систем, который изучает модели преобразователей дискретной инфор­мации, называемые автоматами. Теория конечных автоматов мо­жет быть с успехом использована для моделирования таких объ­ектов, как вычислительные системы, технологические процессы, управляющие и организационные структуры. В общем случае её применение позволяет вычислять, компактно представлять, анализировать и прогнозировать процессы в динамических си­стемах при сложных входных воздействиях [19,20,21].

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

Конечный автомат — это пятерка К = {Q,A,5,\,F}, где

Q — множество конечных состояний автомата;

А — алфавит автомата (конечное множество входных С/, вы­ходных V и промежуточных символов или букв);

S — функция переходов, она задаёт отображение вида 5 : Q х х А —> Q (переход из одного состояния в другое под воз­действием символов входного алфавита);

А — функция выходов, её вид зависит от типа конечного авто­мата;

F — множество выделенных (распознанных) состояний. Дан­ное множество является подмножеством множества Q.

Среди выделенных состояний могут быть, например, состо­яние ошибки или состояние нормального завершения процес­са. Эти автоматы предназначены для решения задач, связан­ных, например, с разбором текста, распознаванием необходимой цепочки символов, анализом анкет, нахождением информации в базе данных и др. Под воздействием последовательности вход­ных сигналов (букв алфавита А) конечный автомат переходит из одного состояния в другое и оказывается в конечном состоя­нии, принадлежащем F, в случае распознания входной последо­вательности. Конечный автомат может быть представлен в виде графа, множество вершин которого соответствует множеству Q.

Из вершины qi в вершину qj ведет дуга, помеченная сим­волом алфавита, если есть соответствующая команда (буква алфавита), которая переводит автомат из состояния qi в состо­яние qj. Последовательность букв интерпретируется при этом как входное слово. Множество допустимых слов образует язык автомата.

УА может быть представлен в виде автомата Мура или авто­мата Мили. Оба типа автомата могут быть использованы для ин­терпретации микропрограммы работы управляющего автомата.

Автомат Мура. Работа автомата Мура описывает­ся функциями переходов и выходов:

Здесь выход зависит от текущего состояния

В качестве примера рассмотрим способ перехода от заданной микропрограммы (рис. 2.8) к графу автомата Мура. Каждой микрокоманде (прямоугольный блок на схеме) поставим в со­ответствие отдельное состояние автомата. Условие перехода от одной микрокоманды к другой (ромб на схеме) представляется в виде конъюнкции осведомительных сигналов, влияющих на переход. Каждая конъюнкция выписывается так, чтобы набор значений осведомительных переменных, обращающих конъюнк­цию в «1», соответствовал условию перехода. При безусловном переходе конъюнкция заменяется на константу «1». Начало и конец микропрограммы отображаются одним и тем же началь­ным состоянием до — Автомат ожидает возникновения сигнала и о = 1, после чего он начинает работать. Автомат вырабатыва­ет в соответствии с заданной микропрограммой управляющие

сигналы и получает осведомительные сигналы. При этом пред­полагается, что управляющий автомат является циклическим, т. е. может выполнять микропрограмму многократно.

Представлен граф автомата Мура, интерпрети­рующего заданную микропрограмму. Функции выхода автомата описываются булевыми функциями:

v\ = 9 1 V Щ = 92 V 94, г’з = q\,

По заданным функциям может быть построена функциональная схема автомата.

Автомат Мили.

Автомат Мили отличается тем, что его функции выхода в момент t зависят не только от состо­яния автомата, но и от набора значений входных осведомитель­ных сигналов:

Построим граф автомата Мили (рис. 2.10). Автомат Мили ис­пользует другие состояния, они определены на выходах. Начало и конец микропрограммы представляется начальным состояни­ем до- Каждая дуга, выходящая из прямоугольника, отмеча­ется меткой и символом состояния автомата. Исключение со­ставляют дуги, идущие к конечной или начальной вершинаам, которые не отмечаются. Если несколько дуг с меткой входит в один блок графа, то они отличаются одинаковым состояни­ем. Условие перехода от одного состояния к другому соседнему

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

Описание выходных сигналов автомата Мили:

Автомат Мили, построенный по микропрограмме управле­ния, имеет число состояний, как правило, меньшее числа состо­яний эквивалентного ему автомата Мура. Однако у автомата Мили есть недостаток, препятствующий его использование в ка­честве УА. Этот недостаток связан с тем, что при смене сигналов на входе изменения на выходе сигналов могут произойти быст­рее, чем произойдёт смена состояния автомата (эффект гонок). Недостаток устраняется введением элементов задержки.

При синтезе автоматов решаются задачи:

•  оптимального кодирования, минимизирующего число со­стояний автомата;

•  перехода от недетерминированного автомата к детермини­рованному автомату.

Методики формального синтеза и оптимизации структуры управляющих автоматов хорошо отработаны. Их целесообраз­но использовать, если взаимосвязь потоков работ представлена в виде микропрограммы.