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

 

Чтобы задать цифровой автомат S, необходимо описать все элементы множества S = { A, X ,Y, d, l, a₁}, то есть входной и выходной алфавиты и алфавит состояний, а также функции переходов и выходов. Из множества способов описания обычно используются практически равноценные табличный и графический (с помощью ориентированных графов) [4].

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

 

Таблица 14 Таблица15

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

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

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

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

Пример табличного описания полностью определённого цифрового автомата Мили S₁ с тремя состояниями, двумя входными и двумя выходными сигналами приведён в таблице 16 и таблице 17.

 

Таблица 16 Таблица 17

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

Заголовочная строка и столбец обозначены одинаково для обеих таблиц, поэтому для экономии времени можно производить описание автомата Мили одной совмещённой таблицей переходов и выходов, например, таблицей 18.

 

Таблица 18

Совмещённая таблица переходов и выходов автомата Мили S₁

Для частичных автоматов, у которых функции d и l определёны не для всех пар (a_m, z_f) Í A´X , на месте неопределённых состояний и неопределённых выходных сигналов ставится какой либо специальный символ, например, прочерк. Пример табличного описания частичного автомата приведён в совмещённой таблице 19.

Таблица 19

Совмещённая таблица для частичного а. Мили S₂

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

 

Таблица 20

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

 

Таблица 21

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

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

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

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

На рис.22, рис.23 и рис.24 приведены графы цифровых автоматов S₁, S₂ и S₃, описанные ранее в таблице 18, таблице 19 и таблице 21

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