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

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

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

A={a1,a2,a3,a4}, Z={z1,z2,z3}, W={w1,w2,w3,w4,w5}.

Строки таблиц отмечены входными символами (элементы множества Z), а столбцы − состояниями (элементы множества А). Входные символы и состояния, которыми помечены строки и столбцы, относятся к моменту времени t. В табл. 26 (таблице переходов) на пересечении строки zi(t) и столбца am(t) ставится состояние as(t+1)=d(am(t),zi(t)). В табл. 27 (таблице выходов) на пересечении строки zi(t) и столбца am(t) ставится выходной символ w(t)=l(am(t),zi(t)), соответствующий переходу из состояния аm в состояние as. Таким образом, по таблицам переходов и выходов можно проследить последовательность работы автомата. Так, например, в начальный момент времени t=0 автомат, находясь в состоянии a1 (первый столбец), под действием входного символа z1 может перейти в состояние a2, при этом выходной символ не формируется; под действием входного символа z2 − в состояние a4 с формированием выходного символа w2; под действием символа z3 − в состояние a3 с формированием выходного символа w3. Далее если на вход автомата, установленного в исходное состояние аm ÍA, в моменты времени t=1,2,…,n подается некоторая последовательность букв входного алфавита (входных символов) ziÍZ, то на выходе автомата будут последовательно формироваться буквы выходного алфавита (выходные символы) wjÍW, при этом автомат будет переключаться в состояния asÍA. Следовательно, с помощью таблиц переходов и выходов можно получить выходную реакцию автомата на любое входное слово.

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

Другим, более наглядным способом описания закона функционирования автомата является представление его в виде графа. Граф автомата – ориентированный граф, вершины которого соответствуют состояниям, а дуги − переходам между ними. Дуга, направленная из вершины am в вершину as, соответствует переходу из состояния am в as. В начале дуги записывается входной символ zi, влияющий на переход as=d(am,zi), а символ wj записывается в конце дуги (автомат Мили) или рядом с вершиной (автомат Мура). На рис. 37 приведен граф автомата Мили, соответствующий закону функционирования, описанному выше (см. табл. 26 и 27).








Дата добавления: 2016-01-09; просмотров: 910;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.005 сек.