Теория автоматов. Аралбаев Т.З - 26 стр.

выражений, язык логических схем алгоритмов, язык граф–схем алгоритмов
(ГСА).
        В автоматных языках поведение ЦА задается путем явного описания
функции переходов и выходов, в частности с использованием уточненных графов
переходов и выходов, таблиц переходов и выходов, матриц переходов и выходов.
        Рассмотрим задачи формирования табличной и графической форм задания
конечных автоматов. В качестве исходных данных будем использовать ГСА
микропрограмм.
        По ГСА можно построить графы и таблицы переходов-выходов
микропрограммного автомата, соответствующие автомату Мура или Мили. Для
этого на ГСА нужно отметить (указать) символы состояний автомата. Существует
несколько способов разметки ГСА ЦА. Рассмотрим один из них. Будем полагать,
что автомат начинает работу с состояния s0, в котором он не вырабатывает
никаких выходных сигналов и после выполнения микропрограммы снова
оказывается в этом же состоянии. Затем автомат переходит в состояния,
предписанные законом функционирования, и формирует микрокоманды из
заданного множества Y. Момент окончания выполнения микропрограммы
отмечается возвратом автомата в начальное состояние s0.
        Отметка состояний на ГСА должна соответствовать закону
функционирования автомата Мура или Мили, то есть выполняется различным
образом.
        Для автомата Мура выходные сигналы связаны только с состоянием
автомата, поэтому каждой операторной вершине ГСА нужно поставить в
соответствие одно из состояний автомата. Правило разметки состояний автомата
на ГСА выглядит следующим образом:
    - символом s0 отмечаются начальная и конечная вершины ГСА, при этом
символ состояния ставится рядом с вершиной;
    - каждая операторная вершина отмечается единственным символом из
списка: s1, s2, s3, s4, s5, ...; две и более различные операторные вершины не могут
быть отмечены одинаковыми символами.
        На рисунке 5.1 представлена ГСА, размеченная для автоматов Мура и
Мили. В каждом такте автомат Мура, интерпретирующий данную микропро-
грамму, переходит из одного состояния в другое и выдаѐт соответствующие
выходные управляющие сигналы yi. Так, при наличии входного сигнала х1 = 0
автомат из состояния s0 перейдет в состояние s1 и выдаст выходной сигнал у1. В
следующем такте работы под воздействием входного сигнала х2 = 1 автомат из
состояния s1 перейдѐт в состояние s3 с выдачей выходных сигналов у2 и у3.
        Если для реализации ГСА используется автомат Мили, то разметка граф-
схемы алгоритма производится в следующем порядке:
      - символом s0 отмечается выход начальной и вход конечной вершины;
      - символами: s1, s2, ... - отмечаются входы вершин, следующие за
операторными вершинами;
      - входы двух различных вершин не могут быть отмечены одинаковыми
символами;
      входы вершины могут отмечаться только одним символом состояния.
26