4.8. Синтез автомата Мили

На этапе получения отмеченной ГСА входы вершин, следующих за операторными, отмечают символами a₁, a₂, … по следующим правилам:

1) символом отмечают вход вершины, следующей за начальной вершиной, а также вход конечной вершины;

2) входы всех вершин следующих за операторными вершинами, должны быть отмечены;

3) входы различных вершин, за исключением конечной вершины, отмечаются различными символами;

4) если вход вершины отмечается, то только одним символом.

Ясно, что для проведения отметок потребуется конечное число символов . Результатом первого этапа является отмеченная ГСА, которая служит основой для второго этапа - перехода к графу или таблицам переходов-выходов. Пример ГСА, отмеченной для автомата Мили, представлен на рис. 4.15.

На втором этапе используя отмеченную ГСА создают граф автомата или таблицы переходов-выходов. При этом полагают, что в автомате будет ровно столько состояний, сколько символов понадобилось при отметке ГСА.

Для каждого из состояний отмеченной ГСА определяем все пути, ведущие в другие состояния и проходящие только через одну операторную вершину. Например, из состояния имеется переход в состояниеи в состояние. Переходанет, так как этот путь не проходит ни через одну операторную вершину. Будем считать, что автомат осуществляет переход, например, извпри условии, и вырабатывает на этом переходе выходные сигналы(см. рис. 4.15). Это означает, что значения условий,,на этом переходе не оказывают влияния на автомат.

Рис. 4.15. Отмеченная ГСА автомата Мили

Исключение составляет только один путь, ведущий в конечную вершину, он может не содержать ни одной операторной вершины (например, переход из в), т.е. он не сопровождается выработкой выходных сигналов.

Отмечаем на графе все указанные пути для всех состояний в виде дуг, которым приписываем условия перехода и выходной сигнал, вырабатываемый на этом переходе. Получим граф автомата (рис. 4.16).

Рис. 4.16. Граф автомата Мили

На этом графе переходам типа ,приписывается условие перехода 1, т.к. эти переходы являются безусловными и выполняются всегда, когда автомат попадает в состояние(или).

На основании отмеченной ГСА или графа автомата можно построить таблицу переходов-выходов. Для микропрограммных автоматов таблица переходов-выходов строится в виде списка и различаются как прямая и обратная таблицы. Для данного автомата прямая таблица представлена табл. 4.14, а обратная - табл. 4.15.

В приведенных таблицах - исходное состояние,- состояние перехода,- условие (входной сигнал), обеспечивающий переход из состоянияв состояние,- выходной сигнал, вырабатываемый автоматом при переходе изв.