19.Абстрактные конечные автоматы 1-го и 2-го рода. Матрицы переходов и выходов. Представление графом.

Абстрактный автомат задается как совокупность шести объектов:

• конечного множества Х входных сигналов (т.н. входной алфавит автомата);

• конечного множества Y выходных сигналов (выходной алфавит автомата);

• произвольного множества А, называемого множеством состояний автомата;

• элемента а₀А, называемого начальным состоянием автомата;

• функций переходов (а,x) и выходов (а,x), задающих однозначные отображения множества (а,x), где аА и xX, в множества А и Y.

Абстрактный автомат функционирует в дискретном времени, в каждый момент этого времени имеет определенное состояние а(t) из множества А состояний автомата. В каждый момент времени, отличный от начального, автомат способен воспринимать входной сигнал x(t) – произвольную букву входного алфавита X и выдавать соответствующий выходной сигнал y(t) – определенную букву выходного алфавита.

Закон функционирования автомата первого рода задается уравнениями:

В практике как правило используют:

• автомат Мили – произвольный конечный автомат первого рода;

• автомат Мура – частный случай конечных автоматов второго рода, у кот. функция выходов (а,x) не зависит от переменной х.

Автомат называется конечным если конечно число его состояний.

Автоматы задают табличным способом или направленным графом. В первом случае строят матрицы переходов и выходов. Строки обеих этих таблиц обозначаются входными сигналами автомата, а столбцы – его состояниями. На пересечении строки и столбца таблицы переходов ставится соответствующее значение функции переходов (а,x), а в таблице выходов – значение (а,x).

Для автомата Мура сдвинутая таблица выходов сводится по существу к одной строке, поэтому часто в таблице переходов над каждым состоянием а_i автомата, обозначающим тот или иной столбец таблицы, ставят соответствующий этому состоянию выходной сигнал  (а_i,x)= (а_i).

При задании автомата с использованием направленного графа вершины графа отождествляются с состояниями автомата, а стрелки – с выходными сигналами. Если входной сигнал x_i вызывает переход автомата из состояния а_j в состояние а_k, то на графе автомата этому сигналу соответствует помеченная буквой x_i стрелка, соединяющая вершину, соответствующую состоянию а_j, с вершиной, соответствующей состоянию а_k. Для задания функции выхода ребра графа также помечаются соответствующими выходными сигналами. Если обозначенная входным сигналом x_i стрелка соединяет вершину а_j с а_k, то в случае автоматов первого рода ей предписывается выходной сигнал (а_j,x_i), а в случае автоматов второго рода – выходной сигнал (а_k,x_i).

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