Абстрактная и структурная теории конечных автоматов. Структура операционного устройства. Способы задания автоматов, страница 5

Классическая модель коллективного поведения автоматов – это предельный случай описания реактивных агентов, которые обладают минимальной автономностью и целеполаганием, поведение которых корректируется из некоторого центрального устройства управления.

При использовании автоматных языков поведение автомата задается путем явного задания функций переходов и выходов. Наиболее часто используются табличный и графический способы задания работы автомата. При табличном способе задания автомата Мили, функции переходов и выходов задаются соответственно таблицей переходов и таблицей выходов. Строки обеих таблиц обозначаются входными сигналами автомата, а столбцы - его состояниями. На пересечении i-ой строки и j-го столбца таблицы переходов ставится соответствующее значение d(a_j,z_i) функции переходов, а в таблице выходов соответствующее значение l(a_j,z_i) функции выходов. Автомат Мура задается одной отмеченной таблицей переходов, в которой таблица выходов имеет лишь одну строку и совмещается с таблицей переходов (рис.1.2).

При графическом способе задания автомата функции переходов и выходов задаются с помощью ориентированного связного графа, вершины которого соответствуют состояниям, а дуги - переходам между ними. Переходы из состояния a_m в состояние a_s под действием входного сигнала z_f для автоматов Мили и Мура показаны на рис.1.3.

Если переход автомата происходит под действием нескольких входных сигналов, то дуге (a_m,a_s) приписываются все эти входные и соответствующие выходные сигналы. Выходной сигнал w_p=l(a_j) автомата Мура записывается рядом с соответствующей вершиной a_j. Могут быть случаи, когда не все значения функций переходов и выходов определены. Автоматы с такими функциями называются частично определенными. При этом в тех местах таблицы переходов и таблицы выходов, где соответствующие функции неопределенны, проставляются прочерки (рис.1.4).