Теория автоматов. 8.Синтез микропрограммного автомата Мили по ГСА

Этапы:

1. Получение отмеченной ГСА.

2. Построение графа микропрограммного автомата Мили.

Состояния автомата Мили — Метки.

Построение отмеченной ГСА при синтезе Мили заключается в том, что входы вершин, следующих за операторными, отмечаются символами a1, a2,... по правилам:

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

2) входы вершин, следующих за операторными вершинами, отмечаются символами a2, a3,...;

3) входы двух различных вершин (кроме конечной) не могут быть отмечены одинаковыми символами;

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

Соседние метки — метки, между которыми расположена одна операторная вершина.

Путь по ГСА соединяющий соседние метки наз. путём перехода. Каждому пути перехода можно сопоставить набор логических условий и набор микроопераций.

Алгоритм построения графа Мили S состоит из следующих шагов:

1. В качестве состояний автомата выбрать метки {a1,...,a_M},

a1 — начальное состояние.

2. Найти все пути перехода на отмеченной ГСА.

2.1. Если некоторый путь содержит несколько символов x^e_rr, то взять только один символ.

2.2. Если некоторый путь содержит как x_r, так и x_r, то этот путь не рассматривать.

3. Каждому пути перехода a_mX(a_m, a_s) Y(a_m, a_s)a_s поставить в соответствие переход автомата S из состояния a_m в состояние a_s под действием входного сигнала X(a_m, a_s) с выдачей выходного Y(a_m, a_s).

4. Каждому пути перехода a_mY(a_m, a_s)a_s поставить в соответствие переход автомата S из состояния a_m в состояние a_s под действием входного сигнала «1» (конъюнкция пустого мн-ва переменных) с выдачей выходного сигнала Y(a_m, a_s).

5. Каждому пути перехода a_mX(a_m, a₁)a₁ поставить в соответствие переход автомата S из состояния a_m в состояние a₁ под действием входного X(a_m, a₁) с выдачей выходного сигнала Y₀ или «–» (пустой оператор).