Разновидности цифровых автоматов

Классификация цифровых автоматов

Рассмотренные выше абстрактные автоматы можно разделить на:

1) полностью определенные и частичные;

2) детерминированные и вероятностные;

3) синхронные и асинхронные;

Полностью определенным называется абстрактный цифровой автомат, у которого функция переходов и функция выходов определены для всех пар (a_i, z_j).

Частичным называется абстрактный автомат, у которого функция переходов или функция выходов, или обе эти функ­ции определены не для всех пар (a_i, z_j).

К детерминированным относятся автоматы, у которых выполнено условие однозначности переходов: автомат, находя­щийся в некотором состоянии a_i, под действием любого входного сигнала z_j не может перейти более, чем в одно состоя­ние.

В противном случае это будет вероятностный автомат, в котором при заданном состоянии a_i и заданном входном сиг­нале z_j возможен переход с заданной вероятностью в различные состояния.

Для определения синхронных и асинхронных автоматов вводится понятие устойчивого состояния. Состояние a_s автомата называется устойчивым, если для любого состояния a_i и входного сигнала z_j таких, что d(a_i, z_j) = a_s имеет место d(a_s, z_j) = a_s, т.е. состояние устойчиво, если попав в это состояние под действием некоторого сиг­нала zj, автомат выйдет из него только под действием другого сигнала z_k, отличного от z_j.

Автомат, у которого все состояния устойчивы - асинхронный.

Автомат называется синхронным, если он не является асинхронным.

Абстрактный автомат называется конечным, если конечны множества А = {a₁, a₂,..., a_m}, Z = {z₁, z₂,..., z_f}, W = {w₁, w₂,..., w_g}. Автомат носит название инициального, если в нем выделено начальное состояние a₁.

На практике наибольшее распространение получили два класса автоматов - автоматы Мили (Mealy) и Мура (Moore).

Закон функционирования автомата Мили задается уравнениями:

a(t+1) = d(a(t), z(t)); w(t) = l(a(t), z(t)), t = 0,1,2,...

Закон функционирования автомата Мура задается уравнениями:

a(t+1)=d(a(t), z(t)); w(t) = l(a(t)), t = 0,1,2,...

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

Кроме автоматов Мили и Мура иногда оказывается удобным пользоваться совмещенной моделью автомата, так на­зываемым С- автоматом.

Абстрактный С- автомат можно представить в виде устройства с одним входом, на который поступают сигналы из входного алфавита X, и двумя выходами, на которых появляются сигналы из алфавитов Y и U. Отличие С - автомата от моделей Мили и Мура состоит в том, что он одновременно реализует две функции выходов l₁ и l₂, каждая из которых характерна для этих моделей в отдельности. Закон функционирования С- автомата можно описать следующими уравнениями:

а(t+1) =d(a(t), z(t)); w(t) =l₁(a(t), z(t)); u(t) = l₂(a(t)); t = 0, 1, 2,...

Выходной сигнал U_h=l₂(a_m) выдается все время, пока автомат находится в состоянии a_m. Выходной сигнал Wg=l₁(a_m, z_f) выдается во время действия входного сигнала Z_f при нахождении автомата в состоянии a_m.