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

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

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

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

- множества состояний автомата А;

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

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

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

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

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

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

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

Автомат называется конечным если конечно число его состояний. Автоматы задают табличным способом или направленным графом. В первом случае строят матрицы переходов и выходов. Строки обеих этих таблиц обозначаются входными сигналами автомата, а столбцы – его состояниями. На пересечении строки и столбца таблицы переходов ставится соответствующее значение функции переходов j(а,x), а в таблице выходов – значение y(а,x). Для автомата Мура сдвинутая таблица выходов сводится к одной строке, поэтому часто в таблице переходов над каждым состоянием а_i автомата, обозначающим тот или иной столбец таблицы, ставят соответствующий этому состоянию выходной сигнал j (а_i,x) = y(а_i).

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