Построение по ГСА автоматов Мили

 

 

 

См. методичку

Першеев В.Г. «Построение МПА»,

раздел 8.

 

 

 

 

Построение по ГСА автоматов Мура.

 

 

См. методичку

Першеев В.Г.«Построение МПА»,

раздел 9.

 

 

 

 

 

Построение автоматов по МСА.

 

 

Если ГСА чрезмерно громоздки, авто-

маты строят по МСА.

Кроме того, по уточненным недоопре-

деленным МСА можно строить МПА,

не доопределяя МСА при переходе к

ГСА. Это дает недоопределенные МПА,

которые обычно хорошо минимизиру-

ются.

 

 

Автоматы Мура.

Кн и Кк соответствуют S₀.

К_i соответствует S_i.

Набор микроопераций в К_i соответству-

ет набору выходных сигналов, отмечаю- щих состояние S_i. Условия перехода из

S_i в S_j те же, что из К_i в К_j.

 

 

 

Автоматы Мили.

Кн и Кк, а также микрокоманды, за ко- торыми идут переходы только к Кк, со- ответствуют S₀.

Остальные К_i соответствуют S_i.

Условия переходов, как и для автома-

тов Мура, берутся прямо из МСА. Пе-

реходы из S₀ берутся только для Кн.

 

 

Выходные сигналы при переходе выпи- сываются по микрооперациям тех мик- рокоманд, в которые идет переход по МСА. Получаемый автомат имеет как правило «лишние» (эквивалентные) сос- тояния, но они пропадут при минимиза-

ции МПА.

 

 

 

3.10 Описание МПА таблицами переходов.

 

 

Автоматы с большим числом состояний описывают не графами, а таблицами (из-

за громоздкости). При этом используют прямую таблицу переходов (ПТП), либо обратную таблицу переходов (ОТП).

 

ПТП поочередно описывает все перехо-

ды из каждой вершины (все существую- щие). Описание в виде ПТП обычно ис- пользуется при решении задач анализа, например, при поиске совместных сос- тояний при минимизации (см. 3.11).

 

Пример для автомата Мура.

 

 

Пример для автомата Мили.

 

 

295

 

 

ОТП поочередно описывает все перехо-

ды в каждую вершину.

Описание в виде ОТП обычно использу- ется при решении задач синтеза.

 

 

Пример для автомата Мура.

 

 

Пример для автомата Мили.

 

 

 

Таблицы переходов удобны и для «руч- ного» и для «машинного» решения за- дач.

 

 

 

 

Минимизация МПА.

 

 

См. методическое пособие

Каган Б.М., Першеев В.Г. «Синтез МПА», раздел 3. См. также лекции раздел 2.

 

Минимизация МПА с поиском эквива-

лентных состояний чрезмерно трудоем-

ка из-за большого числа двоичных вхо-

дов и, следовательно, комбинаций вход-

ных значений.

 

 

МПА обычно минимизируют приближе- нно (не полностью), используя понятие совместимости состояний (частный слу-

чай эквивалентности).

Совместимые состояния можно склеи- вать в одно.

 

У автомата Мура S_i и S_j совместимы, если

 

 

таковы, что для любого Х:

Ф ( X, S_i ) = Ф ( X, S_j ) , либо

Ф ( X, S_i ) - не определено, либо

Ф ( X, S_j ) - не определено.

 

 

 

И одновременно

 

F(S_i) = F(S_j) , либо

F(S_i) - не определено, либо

F(S_j) - не определено

 

Для автоматов Мили условия совмести-

мости S_i и S_j аналогичны:

для любого Х

Ф ( X, S_i ) = Ф ( X, S_j ) , либо

Ф ( X, S_i ) - не определено, либо

Ф ( X, S_j ) - не определено.

 

 

И одновременно

 

F(Х, S_i) = F(Х, S_j) , либо

F(Х, S_i) - не определено, либо

F(Х, S_j) - не определено

 

Примеры (автоматы Мили)

 

 

 

 

Примеры (автоматы Мура)

 

 

 

 

 

 

Склеивая совместимые состояния ( в пе- рвую очередь с наиболее схожими функ- циями переходов и выходов) мы мини- мизируем автомат.

Отношения совместимости у нескольких состояний в процессе склеивания их мо-

гут меняться.

Алгоритм склеивания см. в методичке.