2.2. Методы описания цифровых автоматов

Чтобы задать цифровой автомат S, необходимо описать все элементы множества S = {A, X ,Y, , , a₁}, то есть входной и выходной алфавиты и алфавит состояний, а также функции переходов и выходов.

Пример общего описания автоматов Мили таблицами переходов и выходов дан в таблице 2.1 и таблице 2.2.

Таблица 2.1

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

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

Таблица 2.2

Общий вид таблицы выходов

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

Строки этих таблиц соответствуют входным сигналам множества X, а столбцы – состояниям A, причём крайний левый столбец обозначен как начальное состояние инициального цифрового автомата a1.

На пересечении столбца am и строки zf в таблице переходов ставится состояние a_s=(a_m, z_f), в которое автомат переходит из состояния a_m под действием сигнала z_f. В таблице выходов - соответствующий этому переходу выходной сигнал w_g=(a_m, z_f).

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

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

Две вершины графа автомата a_m и a_s (исходное состояние и состояние перехода) соединяются дугой, направленной от a_m к a_s , если в автомате имеется переход из a_m в a_s , то есть если a_s = (a_m, z_f) при некотором z_f X. Дуге (a_m, a_s) графа автомата приписывается входной сигнал z_f и выходной сигнал w_g = (a_m, z_f), если он определён, и ставится прочерк в противном случае. Если переход автомата из состояния a_m в состояние a_s происходит под действием нескольких входных сигналов, то дуге (a_m, a_s) приписываются все эти входные и соответствующие выходные сигналы.

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

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