В детерминированных автоматах поведение и структура автомата в каждый момент времени однозначно определены текущей входной информацией и состоянием автомата. Состояние автомата аiв данный момент времени определяется состоянием его элементов памяти S. В цифровых устройствах в качестве элементов памяти используются триггеры - элементарные автоматы с двумя состояниями, обладающие полными системами переходов и выходов.
Под действием входных сигналов автомат переходит из одного состояния в другое. Входные сигналы подаются в дискретные интервалы времени. Существует два способа введения автоматного времени, по которым цифровые автоматы делят на синхронные и асинхронные. В асинхронных автоматах моменты перехода автомата из одного состояния в другое заранее не определены и зависят от некоторых событий. В таких автоматах интервал дискретности является переменным. В синхронных автоматах моменты времени, в которых фиксируются изменения состояний автомата, задаются генератором синхросигналов. Промежуток между двумя последовательными моментами дискретного времени есть один такт работы автомата. При этом любая комбинация сигналов, передаваемых одновременно по реальным входным каналам (входное слово), рассматривается как один сигнал. Выходной сигнал является результатом работы автомата.
Функция переходов d однозначно определяет состояние аs, в которое переходит автомат из исходного состояния аmпод действием входного сигнала zf , то есть аs=d(аm,zf). Функция выходов lопределяет выходной сигнал, в зависимости от состояния автомата и входного сигнала, то есть wg=l(аm,,zf ).
В случае, когда множество А состоит из одного состояния, то есть А={a1}, получаем вырожденный абстрактный автомат, у которого выходной сигнал не зависит от предыстории этого автомата, а зависит только от входного сигнала.
Выделяют два типа автоматов:
1) автомат первого рода, или автомат Мили (Mealy), функционирование которого задаётся уравнениями:
a(t) = d(a(t-1), z(t)),
w(t) = l (a(t-1), z(t)).
2) автомат второго рода, заданный уравнениями:
a(t) = d (a(t-1), z(t)),
w (t) = l (a(t), z(t)).
Реальный физический выходной сигнал w(t), отнесенный к моменту времени t, появляется всегда после соответствующего этому же моменту времени входного сигнала z(t). Что же касается момента перехода автомата из состояния a(t-1) в состояние a(t), то сигнал w(t) может фактически появиться либо раньше, либо позже этого момента. В первом случае (автомат Мили) принимается, что выходной сигнал w(t) однозначно определяется входным сигналом z(t) и состоянием a(t-1) автомата в предыдущий момент времени. В случае автомата второго рода сигнал w(t) однозначно определяется парой z(t), a(t).
Особый интерес на практике представляют автоматы второго рода, у которых выходной сигнал w(t) определяется одним лишь его состоянием и не зависит явно от входного сигнала z(t), то есть w(t)=l(a(t)). Такие автоматы называются автоматами Мура (Moore).
Абстрактный автомат можно представить в виде совмещенной модели автомата с одним входом, на который поступают сигналы из входного алфавита Z, и двумя выходами, на которых появляются сигналы из выходных алфавитов W1 , W2. Отличие такого автомата от моделей Мили и Мура состоит в том, что он одновременно реализует две функции l1, l2, каждая из которых характерна для этих моделей в отдельности. Этот автомат задается следующей системой уравнений:
a(t+1) = d (a(t), z(t)),
w1(t) = l1(a(t), z(t)),
w2(t) = l2(a(t)).
Выходной сигнал w1=l1(am,zf) выдается во время действия входного сигнала zf при нахождении автомата в состоянии am , выходной сигнал w2=l2(am) присутствует все время, пока автомат находится в состоянии am.
1.2. Способы задания автоматов
При описании автомата на поведенческом уровне функции переходов и выходов обычно явно не заданы. Поведение автомата описывается в терминах входных и выходных последовательностей, реализуемых отображений, сообщений или управляющих последовательностей сигналов. При описании алгоритмов функционирования автомата на данном уровне наиболее часто используются язык граф-схем алгоритмов или диаграммы состояний и переходов в одной из объектно-ориентированных нотаций.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.