Лекции по "Программированию"

                             Z                                                              W

Рисунок 1 Абстрактный автомат

Абстрактный автомат имеет один вход и один выход. Автомат работает в дискретном времени, принимающем целые неотрицательные значения t = 0,1,2,... В каждый момент t дискретного времени автомат находится в некотором состоянии а(t) из множества состояний автомата, причем в начальный момент t = 0 он всегда находится в начальном состоянии а(0)=а1. В момент t, будучи в состоянии а(t), автомат способен воспринять на входе букву входного алфавита z(t) Z. В соответствии с функцией выходов он выдаст в гот же момент времени t букву выходного алфавита W(t)=λ(a(t), z(t)) и в соответствии с функцией переходов перейдет в следующее состояние а(t+1)=δ[a(t), z(t)], a(t) A, w(t) W.

Абстрактные автоматы можно  разделить на следующие типы:

1. полностью определенные и частичные:
2. детерминированные и вероятностные:
3. синхронные и асинхронные;

Полностью определенным называется абстрактный цифровой автомат, у которого функция переходов и функция выходов определены для всех пар ( а_i ,z_j). Частичным называемся абстрактный автомат, у которого функция переходов или функция выходов, или обе эти функции определены не для всех пар ( а_i ,z_j). К детерминированным относятся автоматы, у которых выполнено условие однозначности переходов: автомат, находящийся в некотором состоянии а_i, под действием любого входного сигнала z_j не может перейти более, чем в одно состояние. В противном случае по будет вероятностный автомат, в котором при заданном состоянии а_i, и заданном входном сигнале z_j возможен переход с заданной вероятностью в различные состояния. Для определения синхронных и асинхронных автоматов вводится понятие устойчивого состояния. Состояние а_s автомата называется устойчивым, если для любого состояния а_i и входного сигнала z_j таких, что δ (а_i ,z_j) = а_s имеет место δ (а_s ,z_j) = а_s, т.е. состояние устойчиво, если попав в это состояние под действием некоторого сигнала z_j, автомат выйдет из него только под действием другого сигнала z_к отличного от z_j.

Автомат, у которого все  состояния устойчивы – это асинхронный автомат. Автомат называется синхронным, если он  не является асинхронным. Абстрактный автомат называется конечным, если конечны множества      А, Z и W. Автомат носит название инициального, если в нем выделено начальное состояние а₁.

Лекция № 16. Синтез микропрограммных автоматов. Синхронные и асинхронные автоматы.  Конечные и инициальные автоматы.  Автоматы Мура

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

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

Теоретическим обоснованием канонического метода структурного синтеза автоматов служит теорема  о структурной полноте:

Всякая система элементарных автоматов, которая содержит автомат  Мура с нетривиальной памятью, обладающая полной системой переходов и полной системой выходов и какую либо функционально-полную систему логических элементов, является структурно полной. В этом случае задача структурного синтеза произвольных автоматов сводится к задаче структурного синтеза комбинационных схем. Результатом канонического метода структурного синтеза является  система логических уравнении, выражающая зависимость выходных сигналов автомата и сигналов, подаваемых на входы запоминающих элементов, от сигналов, приходящих на вход всего автомата в целом, и сигналов, снимаемых с выхода элементов памяти. Эти уравнения называются каноническими. Для правильной работы схем сигналы на входе запоминающих элементов не должны непосредственно участвовать в образовании выходных сигналов, которые по цепям обратной связи подавались бы в тот же самый момент времени на эти входы. Поэтому запоминающими элементами должны быть не автоматы Мили, а автоматы Мура. Таким образом, структурно полная система элементарных автоматов должна содержать хотя бы один автомат Мура. В то же время, для синтеза автоматов с минимальным числом элементов памяти, необходимо в качестве таких элементов выбирать автоматы Мура, имеющие полную систему переходов и полную систему выходов - полные автоматы. Полнота системы переходов означает, что для любой упорядоченной пары состояний автомата найдётся входной сигнал, переводящий первый элемент этой пары во второй, т.е в таком автомате в каждом столбце таблицы переходов должны встречаться все состояния автомата. Полнота системы выходов автомата Мура состоит в том, что каждому состоянию автомата поставлен в соответствие свой особый выходной сигнал, отличный от выходных сигналов других состояний. Т.о. в таком автомате число выходных сигналов равно числу состояний автомата. В связи с этим, в автоматах памяти будем использовать одни и те же обозначения и для состояний, и для выходных сигналов.