Недетерминированные автоматы в проектировании систем параллельной обработки. Вашкевич Н.П. - 91 стр.

логических условий логическое условие x1 не станет равным единице. После
этого выполняется оператор A4 или как было отмечено выше. Выполнение
алгоритма закончится оператором Ak .
         4.3.2. Построение таблиц переходов и СКУ по ГСА
      СКУ в принципе можно построить сразу непосредственно по ГСА,
поставив в соответствие каждой операторной вершине событие СКУ,
учитывая при этом, что одинаковым операторам, стоящим в разных местах
ГСА, должны соответствовать разные события. Однако для облегчения
процесса построения СКУ целесообразно сначала по ГСА построить прямую
таблицу переходов для событий, которая будет соответствовать прямой
таблице переходов автомата, т.к. рассматриваемый вид ГCA не допускает
параллельных ветвей алгоритма. По прямой таблице переходов строится в
дальнейшем СКУ. Тем более, что во многих случаях прямая таблица
переходов автомата используется для структурного синтеза автомата и
самостоятельно. Таким образом, построенная по ГСА СКУ будет
детерминированной всегда и каждому событию СКУ будет соответствовать
свое вполне определенное состояние автомата.
      Алгоритм построения СКУ для автомата Мура будет включать
следующие этапы:
      1) Разметить (пронумеровать) все вершины ГСА, предварительно введя
пустые операторные вершины, если в ГСА имеются циклы из условных
вершин. Пустые операторные вершины размещают при выходе из условной
вершины, определяющей начало пути в цикле из условных вершин.
      2) Каждому оператору ГСА поставить в соответствие вполне
определенное событие (состояние автомата), присвоив ему индекс,
соответствующий номеру вершины ГСА. При этом необходимо иметь ввиду,
что одинаковым операторам, стоящим в разных местах ГСА, должны
соответствовать разные события (состояния автомата). Это обеспечивается
сквозной нумерацией вершин исходной ГСА. Начальной вершине ГСА будет
соответствовать начальное событие S 0 (начальное состояние автомата a 0 ).
Часто начальную и конечную вершины ГСА совмещают, тогда автомат после
выполнения программы алгоритма переходит в начальное состояние.
      3) Заготовить прямую таблицу переходов, как это выполнялось в гл.2, и
отметить каждую строку в столбце 2 обозначением одного из исходных
событий (состояний автомата), начиная с начального события. Осуществить
просмотр всех путей перехода от исходного события (состояния автомата) в
момент времени ( t ) к событиям (состояниям автомата) в конце пути в
момент времени ( t  1). Каждый такой путь должен соответствовать шагу
алгоритма и состоять только из логических условий (условных вершин).
      Каждому пути из логических условий от одного оператора к другому
сопоставить конъюнкцию (сочетание) входных сигналов, т.е. частный
входной сигнал автомата X i , j . Причем в эту конъюнкцию элементарный


                                                                         91