По заданному табличному представлению автомата построить систему его команд.
Пусть конечный автомат имеет алфавиты X = {a, b}, Y = {а, b, с}, Q = {1, 2, 3}, а автоматные функции задаются таблицами:
Представленные две таблицы можно объединить в одну, условившись в каждую клетку на первую позицию ставить значение Y(qr, xk), а через запятую на вторую позицию помещать значение Q(qr, xk). В результате получится следующая «сводная» таблица:
Видно, что таблица стала весьма напоминать таблицу, задающую функциональную схему машины Тьюринга (см. п.7.3.3). Из нее легко просматриваются команды преобразования, осуществляемые данным автоматом:
Пусть на начальном такте автомат находится в состоянии q0 = 1 и на его вход в последующие такты подается последовательность abb. Пользуясь перечнем команд можно установить, что автомат преобразует эту последовательность в bсс и при этом окажется в состоянии 3.
Другой вариант описания автоматных функций - графический. Он обладает большей наглядностью, чем табличный. Состояния автомата <X, Y, Q, Y, Q> задается посредством ориентированного графа, который называется диаграммой (точнее, диаграммой Мура). Вершины графа помечены символами из алфавита состояний автомата Q, а каждой команде qixr → qjys соответствует ребро, идущее из вершины qi в вершину qj, при этом ребру приписывается метка xrys. Таким образом, ребро возникает в том случае, если автомат, находящийся в состоянии qi, посредством некоторого входного сигнала xr может быть переведен в состояние qj. Если такой перевод возможен при нескольких входных воздействиях (хг)(1)..... (хr)(п), и при этом формируются выходные сигналы (ys)(1),..., (ys)(п), то ребру приписывается выражение ((хr)(1), (ys)(1)) v ((хr)(2), (ys)(2)) v...v((xr)(n),(ys)(n).
Для диаграмм, представляющих конечный автомат, справедливы следующие утверждения:
1. из одной вершины не может выходить двух ребер с одинаковым входным символом (условие однозначности);
2. если при работе автомата реализуется входная комбинация qixr, то обязательно существует ребро, идущее из вершины qi помеченное символом хr (условие полноты);
3. количество вершин и ребер диаграммы является конечным.