3. Классификация дискретных автоматов.

По способу формирования интервалов дискретности дискретные автоматы делят на два класса - синхронные автоматы и асинхронные. В синхронных ав­томатах моменты времени, в которых фиксируются изменения состояний ав­томата, задаются специальным устройством - генератором синхросигналов, выдающим импульсы через равные промежутки времени (постоянный интервал дискретности). В асинхронных автоматах моменты перехода автомата из од­ного состояния в другое заранее не определены и зависят от каких-то событий, например, от темпа поступления входных сигналов. В таких автоматах интер­вал дискретности является переменным.

По объему памяти дискретные автоматы подразделяются на:

1) дискретные автоматы с большим объемом памяти;

2) дискретные автоматы с малым объемом памяти;

3) дискретные автоматы с одним состоянием (комбинационные или функциональные автоматы).

К дискретным автоматам с большим объемом памяти относятся модели раз­личных запоминающих устройств.

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

Комбинационным автоматом называется дискретный автомат, имеющий одно внутреннее состояние, определенное типами и характером соединения элементов схемы автомата.

Это частный случай ДА. Для комбинационных автоматов характерна одно­значная зависимость между входными и выходными сигналами в каждый мо­мент времени.

К комбинационным автоматом относятся преобразователи кодов, шифра­торы, дешифраторы, мультиплексоры, комбинационные сумматоры и др.

В особый класс выделяют бесконечные автоматы, у которых множества и Q, X, и Y могут быть бесконечными. Такие автоматы являются моделями вы­числительных машин, поведение которых определяется не только внутренней структурой, но и записанной программой.

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

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

Дискретный автомат, для которого выходной сигнал зависит от входного сигнала и состояния, то есть λ: QXY, называется автоматом Мили.

Дискретный автомат, для которого выходной сигнал зависит только от со­стояния и не зависит от входного сигнала, то есть λ: QY, называется авто­матом Мура.

Кроме того, в зависимости от способа определения выходного сигнала в синхронных автоматах существуют две возможности:

1) выходной сигнал y(t) однозначно определяется входным сигналом x(t) и состоянием q(t-1) автомата в предшествующий момент – это автомат первого рода;

2) выходной сигнал y(t) однозначно определяется входным сигналом x(t) и состоянием q(t) в данный момент времени – это автомат второго рода.

Следовательно, закон функционирования дискретного синхронного автома­та может быть задан следующим образом:

для автомата первого рода

(1)

для автомата второго рода

(2)

Между автоматами первого и второго родов существует однозначное соот­ветствие. Предположим, что произвольный автомат S второго рода задан урав­нениями (2). Функцию выхода можно представить в следующем виде

.

Тогда выходной сигнал (2) y(t) можно представить в виде

(3)

Получили новый автомат R первого рода, заданный той же функцией перехода (q,x), что и автомат S, а также функцией выходов λ₁(q,x).

Таким образом, для каждого автомата S второго рода существует эквивалентный ему абстрактный автомат R первого рода, функция выходи которого получается в результате подстановки функции переходов автомата S в его сдвинутую функцию выходов:

.

Между моделями Мили и Мура существует соответствие, позволяющее преобразовать закон функционирования одного из них в другой или обратно. Такое преобразование порождает пару описаний законов функционирования, эквивалентных в том смысле, что им соответствует одинаковая зависимость, между входной X и выходной Y последовательностями.

Совмещенная модель автомата (С-автомат). Абстрактный С-автомат – математическая модель дискретного устройства, для которого заданы следующие параметры:

Q = {q₁(t),q₂(t),…,q_s(t)} - множество состояний;

X = {x₁(t),x₂(t),…,x_n(t)} - входной алфавит;

Y = {y₁(t),y₂(t),…,y_k(t)} - выходной алфавит автомата Мили;

U = {u₁(t),u₂(t),…,u_m(t)} - выходной алфавит автомата Мура;

: QX  Q - функция переходов, реализующая отображение D_  QX в Q;

λ₁: QX  Y - функция выходов, реализующая отображение D_λ1  QX в Y;

λ₂: Q  U - функция выходов, реализующая отображение D_λ2  Q в U;

q₀  Q - начальное состояние автомата.

Абстрактный С-автомат можно представить в виде устройства с одним входом, на который посту­пают сигналы из входного алфавита X, и двумя выходами, на которых появляются сигналы из выходных алфавитов Y и U.

Отличие С-автомата от моделей Мили и Мура состоит в том, что он одновременно реализует две функции вы­ходов λ₁ и λ₂ каждая из которых характерна для этих моделей в отдельности. Этот автомат можно описать следующей системой уравнений:

(4)

Выходной сигнал и = λ₂(q_i), , выделяется все время, пока автомат находится в состоянии q_i. Выходной сигнал y = λ₂(q_i,x_j) выдается во время действия входного сигнала x_j при нахождении автомата в состоянии q_i.

От С-автомата легко перейти к автоматам Мили или Мура (с учетом воз­можных сдвигов во времени на один такт), так же как возможна трансформация автомата Мили в автомат Мура.

Таким образом, дискретный автомат полностью описывается множествами входного и выходного алфавитов и алфавитом состояний, функциями перехо­дов и выходов (Q, X, Y, , λ). В каждый из моментов дискретного времени i автомат, находящийся в определенном состоянии, воспринимает входной сиг­нал - букву входного алфавита x(i)  X, выдает выходной сигнал y(i)  Y - бук­ву выходного алфавита, определяемую функцией выходов , и переходит в новое состояние, определяемое функцией переходов .

С точки зрения структурной теории автоматов С-автомат имеет обобщен­ную структурную схему, представленную на рис. 1.

Автомат содержит три блока - две комбинационные схемы и блок элемен­тов памяти.

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

Вторая схема формирует выходные функции автомата и , как выходные логические функции комбинационного автомата, синтезированные с учетом используемых логических элементов.

Состояние автомата определяется состоянием элементов памяти (триггеров различных типов). Изменению состояния автомата соответствует изменение состояний триггеров. Переключение триггеров происходит под воздействием функций возбуждения таким образом, что состояния автомата меняются в соот­ветствии с функцией переходов .