Способы задания конечных автоматов

Табличный способ. Автомат Мили может быть задан таблицей переходов, определяющей функцию переходов d, и таблицей выходов, определяющей функцию выходов l. Строки этих таблиц со­ответствуют возможным входным сигналам х_f, а столбцы - воз­можным состоянием а_m автомата. В таблице переходов (рис.2, a) на пересечении столбца а_m и строки х_f находится состояние a_s=d(а_m, х_f). В таблице, выходов (рис. 2,б) в аналогичной клетке помещается выходной сигнал y_g=l(а_m, х_f). Как видно, здесь задан автомат, имеющий множества A={a₀, a₁, a₂}; X={x₁, x₂}; Y={y₁, y₂, y₃}.

Так как в автомате Мура выходные сигналы зависят лишь от состояния, то он задается одной так называемой отмеченной таблицей переходов (рис.2,^). В этой таблице над каждым состоянием

Рис.2

а, автомата, обозначающим тот или иной столбец таб­лицы, стоит соответствующий этому состоянию выходной сигнал

y_g=l(a_m)

Графический способ. Этот способ основан на использовании направленных графов. Вершины графов соответствуют состоя­ниям, а дуги - возможным переходам между ними. Две вершины а_m, и а_s графа соединяются дугой, направленной от а_m, к а_s, если существует переход a_s=d(а_m, х_f). Дуге автомата Мили приписывается входной сигнал х_f, и выходной сигнал y_g=l(а_m). В автомате Мура выходной сигнал y_g=l(а_m) записыва­ется внутри вершины а_m. Графы автоматов Мили и Мура, задан­ных таблицами рис.2, представлены на рис.3.

Рис.3

Процедура синтеза конечного автомата в общем случае де­лится на два этапа: этап абстрактного синтеза и этап струк­турного синтеза. Содержанием первого этапа является построе­ние графа или таблиц переходов и выходов и получение множест­ва состояний А с минимальным числом членов [l]. Цель этапа структурного синтеза - построение схемы автомата на заданных логических элементах и элементах памяти.

Согласно теореме о структурной полноте [I] система эле­ментов, из которых может быть построена схема любого конеч­ного автомата, должна содержать логические элементы базиса и в качестве элемента памяти - автомат Мура, обладающий пол­нотой переходов и выходов. Полнота переходов в автомате озна­чает, что для любой пары состояний существует входной сигнал, который переводит автомат из одного состояния в другое. Иначе говоря, в каждом столбце таблицы переходов должны встречать­ся все состояния автомата. Полнота выходов означает, что каж­дое возможное состояние автомата отмечет отличным от других выходным сигналом.

В качестве элементов памяти широко используются элемен­тарные автоматы Мура с двумя состояниями. Каждый из таких ав­томатов выдает два различных выходных сигнала, соответству­ющих двум его различным состояниям. В дальнейшем указанные состояния и соответствующие им выходные сигналы будут обо­значаться одной буквой Q и кодироваться цифрами 0 и I (QI{0,1}).

Элементарный автомат может иметь в общем случае несколько физических вхо­дов, на каждый из которых могут пода­ваться двоичные сигналы. Условное обо­значение элементарного автомата приведено на рис.4. Здесь u_ji, j=1, 2,…,K – сигналы возбуждения элементарного автомата (u_jiI{0, 1}).

рис. 4

Структурная схема конечного автомата (рис.5) состоит из двух основных частей: комбинационной части (КЧ) и запомина­ющей части (34). КЧ строится из логических элементов базиса (ЗЧ) представляет собой набор элементарных автоматов Q₁, Q₂, Q₃.

Рис.5

Каждое состояние абстрактного автомата a_m(m=0,1,…,M) ко­дируется в структурном автомате набором состояний элементар­ных автоматов (Q₁, Q₂,…,Q_k), где R?]log₂(M+1)[ ]a[ означает ближайшее целое число, большее a или равное a , (ес­ли а целое). Каждый входной x_f, f=1,2,…,F и выходной y_g, g=1,2,…,G сигналы абстрактного автомата кодируются наборами значений двоичных сигналов на L, входных (a₁, a₂,….a_L) и N выходных (Z₁, Z₂,…,Z_N) каналах структурного автома­та. Здесь L?]log₂F[; N?] log₂(G)[.

Изменение состояний элементарных автоматов происходит под действием сигналов возбуждения u_jr, где j=1, 2,…K_r; r = 1, 2,...,R. В схеме рис.5 для простоты у каждого элемен­тарного автомата показано по одному входу u_r

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

Z_n(t)= Z_n[Q₁(t), Q₂(t),…, Q_R(t), a₁(t), a₂(t),…, a_L(t)], n=1,2,…N

u_jr(t)= u_jr[Q₁(t), Q₂(t),…, Q_R(t), a₁(t), a₂(t),…, a_L(t)],

j=1,2,…,K_r; r=1, 2,…, R.