Способы задания автоматов

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

В зависимости от типа автомата при табличном задании закона функционирования автомата используются либо таблицы переходов и выходов (автомат Мили), либо совмещенная таблица переходов и выходов (автомат Мура). С помощью таблиц 26 и 27 задан закон функционирования абстрактного автомата Мили для которого

A={a₁,a₂,a₃,a₄}, Z={z₁,z₂,z₃}, W={w₁,w₂,w₃,w₄,w₅}

Строки таблиц отмечены входными символами (элементы множества Z), а столбцы состояниями (элементы множества А). Входные символы и состояния которыми помечены строки и столбцы относятся к моменту времени t. В таблице 26 (переходов) на пересечении сроки z_i(t) и столбца a_m(t) ставится состояние a_s(t+1)=d(a_m(t),z_i(t)). В таблице 27 (выходов) на пересечении сроки z_i(t) и столбца a_m(t) ставится выходной символ w(t)=l(a_m(t),z_i(t)), соответствующий переходу из состояния а_m в состояние a_s. Таким образом, по таблицам переходов и выходов можно проследить последовательность работы автомата. Так, например, в начальный момент времени t=0 автомат, находясь в состоянии a₁ (первый столбец) под действием входного символа z₁ может перейти в состояние a₂ при этом выходной символ не формируется, символа z₂ в состояние a₄ с формированием выходного символа w₂, z₃ в состояние a₃ с формированием выходного символа w₃. Далее если на вход автомата, установленного в исходное состояние а_m ÍA в моменты времени t=1,2,…,n подается некоторая последовательность букв входного алфавита (входных символов) z_iÍZ, то на выходе автомата будут последовательно формироваться буквы выходного алфавита (выходные символы) w_jÍW, при этом автомат будет переключаться в состояния a_sÍA. Следовательно, с помощью таблиц переходов и выходов можно получить выходную реакцию автомата на любое входное слово.

Как отмечалось выше, для автомата Мура выходной символ не зависит от входного, а определяется только текущим состоянием автомата. Это позволяет для автомата Мура объединить обе таблицы (переходов и выходов) в одну совмещенную таблицу. В совмещенной таблице переходов и выходов каждый столбец отмечается состоянием a_m ÍА и выходным символом w(t)=l(a(t)), соответствующим этому состоянию.

Другим более наглядным способом описания закона функционирования автомата является представление его в виде графа. Граф автомата – ориентированного граф, вершины которого соответствуют состояниям, а дуги переходам между ними. Дуга, направленная из вершины a_m в вершину a_s соответствует переходу из состояния a_m в a_s. Вначале дуги записывается входной символ z_i влияющий на переход a_s=d(a_m,z_i), а символ w_j записывается в конце дуги (автомат Мили) или вначале (автомат Мура). На рис. 36 приведен граф автомата Мили соответствующий закону функционирования, описанному выше (таблицы 26 и 27).