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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 4.14 Прямая таблица переходов-выходов автомата Мили

			-

Таблица 4.15 Обратная таблица переходов-выходов автомата Мили

			-

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

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

Дата добавления: 2015-07-08