Синтез автомата по схеме алгоритма

Синтез автомата Мили начинается с установления связи между определенными этапами выполнения заданного алгоритма и состояниями автомата. Автомат Мили сперва выдает выход­ную букву, а затем изменяет свое состояние. Обе его функции: переходов и выходов зависят от пары "состояние-вход" в момент t:

y(t) = l (a(t), x(t));

a(t+1) = d (a(t), x(t)).

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

Пример 7. На рис. 3.1 показан подграф некоторой схемы алгоритма. Крестиками отмечены входы вершин графа, находящихся сразу за операторами. Крестики должны находиться не у выхо­дов операторных вершин, а именно у входов следующих вершин после всех возможных слияний путей графа. В противном случае число намечаемых состояний неоправданно увеличится.

Рис. 3.1. Исходная схема алгоритма примера 7

Определим переходы автомата из состояния аi в аk. Для этого исследуем все пути на графе, ведущие от отметки аi к отметке аj. Из них нас должны интересовать только пути, содержащие одну операторную вершину графа. Путь через u5 не содержит операторных вершин и в данный момент не представляет интереса. Он понадобится впоследствии, когда будут просматриваться пути от аi к аj. Путь через u5u6y10y11 содержит две операторные вершины и должен соответствовать не одному, а двум переходам автомата.

Остаются два пути, отвечающие поставленному требованию: u5u6u7y12 и u5u6u7y13. Заключаем, что из аi в аk должно быть определено два перехода: при ЛУ u5u6u7 с выдачей у12 и при ЛУ u5u6u7 с выдачей у13. Соответствующий подграф графа переходов автомата Мили показан на рис. 3.2.

Рис. 3.2. Подграф графа переходов автомата Мили

Пример 8. Здесь пара вершин соединена несколькими путями, проходящими через одну и ту же операторную вершину, но при разных ЛУ (рис. 3.3).

Рис. 3.3. Исходная схема алгоритма примера 8

Логические условия такого перехода можно было бы описать дизъюнкцией , но практически такую запись не используют.

Если полученное дизъюнктивное выражение поддается упрощению до элементарной конъ­юнкции, то это упрощение должно быть проделано, и соответствующая часть схемы алгоритма должна быть исправлена. Если же формула не упрощается, то для каждого пути алгоритма опре­деляется отдельный переход. Обозначения отдельных переходов над дугами графа автомата разделяются запятыми. Такое разделение всё равно пришлось бы сделать впоследствии, при структурном синтезе.

Рассуждения, подобные изложенным в примерах 7 и 8, повторяются для каждой пары отметок состояний. Учитываются также замкнутые пути (петли), даже если они не содержат оператора. Такие пустые петли соответствуют режиму ожидания. Если путь приводит в конец алгоритма, то он тоже учитывается, даже если не содержит оператора. Такие пути, как и петли без оператора, отмечаются пустым оператором "е".

Перед началом работы автомат должен находиться в начальном состоянии и в это же состоя­ние должен вернуться по окончании выполнения алгоритма. Поэтому отметка а0 делается как у входа вершины СА, идущей непосредственно после начальной, так и у входа в конечную вершину.

Пример 9. Зададимся СА на рис. 3.4 и, следуя описанной методике, построим граф автомата Мили (рис. 3.5).

Рис. 3. 4. Схема алгоритма примера 9

Рис. 3.5. Граф автомата Мили примера 9

Прежде всего, расставим отметки состояний на СА. Понадобилось шесть отметок, из которых две одинаковых - а0. Затем двигаемся по СА от отметки до отметки, прослеживая все пути согласно описанным правилам.

Как уже говорилось, синтез по СА ведется с использованием структурного алфавита U. Если почему-либо требуется перейти к абстрактному входному алфавиту Х, то ввиду наличия в данном примере четырех структурных переменных u1...u4 число абстрактных букв "х" должно составить
24 = 16. Обычная таблица переходов и выходов имела бы 16 столбцов. Строк же было бы столько же, сколько состояний, т.е. пять.

Структурное представление входного алфавита позволяет применить вместо громоздкой таблицы переходов и выходов список автомата, т.е. таблицу, в которой строка за строкой пере­числяются все имеющиеся в автомате переходы. Для рассмотренного примера список автомата дан в табл. 3.1

Таблица 3.1

Список автомата

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

Синтез автомата Мура по СА выполняется в основном аналогично описанному. Отличия вызваны свойствами функции выходов, которая здесь определяется только состоянием автомата

y(t) = l (a(t)).

Поэтому отметки состояний делаются не в виде крестиков на линиях связи, а непосредственно у операторных вершин СА. Отметка начального состояния а0 ставится у начального и конечного терминаторов алгоритма.

Названное отличие приводит к необходимости корректировать СА, устраняя детали, не поддающиеся реализации в автомате Мура.

Режим ожидания не может быть представлен петлей у проверки логического условия. Необ­ходимо включить в такую петлю пустой оператор "е" или превратить ждущую вершину графа в возвратную вершину (рис. 3.6).

Рис. 3.6. Типы вершин схем алгоритмов

Возвратная вершина выгоднее, чем пропуск такта, так как не добавляет новых состояний, но она может быть организована только тогда, когда содержание оператора уi допускает его повторе­ние (например, можно повторять команду сброса регистра, команду пересылки, но не сдвига или сложения). Если ждущая вершина СА находится в начале алгоритма, то проще всего режим ожи­дания можно организовать, соединив выход этой вершины с конечным терминатором.

Во всех случаях, когда СА содержит петли с двумя или несколькими проверками логических условий (при синтезе любой модели автомата), нужно обратить внимание на правильное замыка­ние этих петель. Дело в том, что проверки логических условий одного перехода выполняются одновременно, и СА должна соответствовать этому требованию (рис. 3.7).

Рис. 3.7. Особенности изображения ветвления в схемах алгоритмов

Пример 10. По той же СА синтезируем автомат Мура. Разметка состояний показана на рис. 3.8.

Рис. 3.8. Схема алгоритма для примера 10

Число состояний автомата Мура оказалось равным семи, т.е. увеличилось на два по сравне­нию с автоматом Мили. Граф автомата строим как в примере 7, но обозначения выходных букв надписываем не над дугами, а над вершинами. Граф автомата Мура показан на рис. 3.9.

Рис. 3.9. Граф автомата Мура для примера 10

Список автомата Мура (табл. 3.2) имеет только три столбца, так как выходные буквы можно записать вместе с состояниями a(t). Составлением списка с абстрактными обозначениями состоя­ний абстрактный синтез заканчивается, так как следующая задача - кодирование состояний отно­сится к уровню структурного синтеза.

Таблица 3.2

Список автомата Мура