Методы задания автоматов

Чтобы задать конечный автомат S, необходимо описать все элементы множества S={A, Z, W, d, l, a₁}.

Табличный способ задания.

Общий вид таблицы переходов Общий вид таблицы выходов автомата Мили автомата Мили

На пересечении столбца a_m и строки z_f На пересечении столбца a_m и строки z_f

Ставится состояние a_s=δ(a_m, z_f), в кото- ставиться выходной сигнал w_y=λ(a_m, z_f),

рое автомат переходит из состояния a_m соответствующий переходу автомата в

под действием сигнала z_f. Состояние a_s.

Пример задания полностью определенного автомата Мили S₁ с тремя состояниями, двумя входными и двумя выходными сигналами.

Таблица переходов автомата Мили S₁ Таблица выходов автомата Мили S₁

Пример задания частично определенного автомата Мили.

Таблица переходов частичного Таблица выходов частичного

автомата Мили S₂ автомата Мили S₂

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

Общий вид отмеченной таблицы Отмеченная таблица переходов

переходов автомата Мура автомата Мура S₃

Графический способ задания

Граф автомата - это ориентированный связный граф, вершины которого соответствуют состояниям, а дуги – переходам между ними.

Две вершины графа автомата a_m и a_s (исходное состояние и состояние перехода) соединяются дугой, направленной от a_m к a_s, если в автомате имеется переход от a_m к a_s, то есть если a_s=d(a_m,z_f) при некотором входном сигнале z_fÎZ.

Дуге (a_m,a_s) графа автомата приписывается входной сигнал z_f и выходной сигнал w_g=l(a_m, z_f), если он определен и ставится прочерк в противном случае.

Граф автомата Мили S₁ Граф автомата Мили S₂

a₁ a₂

a₂ a₃ a₁ a₃

a₄

При описании автомата Мура в виде графа выходной сигнал w_g=l(a_m) записывается внутри вершины a_m или рядом с ней.

Граф автомата Мура S₃

a₁

a₅ a₂

a₄ a₃

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

Состояние a_s автомата S называется устойчивым состоянием, если для любого входа z_fÎZ, такого, что d(a_m, z_f)=a_s, имеет место d(a_s, z_f)=a_s.

Автомат S называется асинхронным, если каждое его состояние a_sÎA устойчиво.

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

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

Отмеченная таблица переходов асинхронного автомата Мура S₄

Граф асинхронного автомата Мура S₄

a₁

a₂ a₃

Если в состояние a_s имеется переход из другого состояния под действием входного сигнала z_f, то в a_s должна быть петля, отмеченная символом z_f.