Теория автоматов — раздел теории управляющих систем, который изучает модели преобразователей дискретной информации, называемые автоматами. Теория конечных автоматов может быть с успехом использована для моделирования таких объектов, как вычислительные системы, технологические процессы, управляющие и организационные структуры. В общем случае её применение позволяет вычислять, компактно представлять, анализировать и прогнозировать процессы в динамических системах при сложных входных воздействиях [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, после чего он начинает работать. Автомат вырабатывает в соответствии с заданной микропрограммой управляющие
Рис. 2.9. Граф автомата Мура |
сигналы и получает осведомительные сигналы. При этом предполагается, что управляющий автомат является циклическим, т. е. может выполнять микропрограмму многократно.
Представлен граф автомата Мура, интерпретирующего заданную микропрограмму. Функции выхода автомата описываются булевыми функциями:
v\ = 9 1 V Щ = 92 V 94, г’з = q\,
По заданным функциям может быть построена функциональная схема автомата.
Автомат Мили.
Автомат Мили отличается тем, что его функции выхода в момент t зависят не только от состояния автомата, но и от набора значений входных осведомительных сигналов:
Построим граф автомата Мили (рис. 2.10). Автомат Мили использует другие состояния, они определены на выходах. Начало и конец микропрограммы представляется начальным состоянием до- Каждая дуга, выходящая из прямоугольника, отмечается меткой и символом состояния автомата. Исключение составляют дуги, идущие к конечной или начальной вершинаам, которые не отмечаются. Если несколько дуг с меткой входит в один блок графа, то они отличаются одинаковым состоянием. Условие перехода от одного состояния к другому соседнему
задают функцию переходов автомата. Эти условия записываются в виде конъюнкции осведомительных сигналов; кроме того, для каждого перехода фиксируется набор выходных переменных, принимающих при переходе единичное значение.
Описание выходных сигналов автомата Мили:
Автомат Мили, построенный по микропрограмме управления, имеет число состояний, как правило, меньшее числа состояний эквивалентного ему автомата Мура. Однако у автомата Мили есть недостаток, препятствующий его использование в качестве УА. Этот недостаток связан с тем, что при смене сигналов на входе изменения на выходе сигналов могут произойти быстрее, чем произойдёт смена состояния автомата (эффект гонок). Недостаток устраняется введением элементов задержки.
При синтезе автоматов решаются задачи:
• оптимального кодирования, минимизирующего число состояний автомата;
• перехода от недетерминированного автомата к детерминированному автомату.
Методики формального синтеза и оптимизации структуры управляющих автоматов хорошо отработаны. Их целесообразно использовать, если взаимосвязь потоков работ представлена в виде микропрограммы.