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

     4.5.3. Построение таблиц переходов и СКУ для цифровых
               автоматов, заданных на языке ГСАП
      Цифровые автоматы, заданные на языке ГСАП, являются
недетерминированными, т.к. отдельные параллельные ветви алгоритма
управления имеют общую вершину, от которой выполняется разветвление
алгоритмического процесса. В связи с этим прямая таблица переходов (ПТП),
соответствующая такому автомату, также будет недетерминированной, хотя
она    и     будет     представлять   собой    совокупность     нескольких
детерминированных ПТП, к числу которых относятся: детерминированные
ПТП, соответствующие отдельным параллельным ветвям исходной ГСАП с
общей начальной вершиной и детерминированная ПТП, которая
соответствует последовательной части алгоритма управления, состоящей из
начальной части до разветвительной вершины и конечной части после
соединительной вершины.
      Недетерминированная ПТП для автомата, заданного на языке ГСАП,
будет строится в два этапа. Сначала строят независимо друг от друга ПТП
для отдельных параллельных ветвей и последовательной части алгоритма
управления также как и для обычных ГСА, а затем выполняют необходимую
коррекцию частных событий, реализуемых алгоритмом управления.
Коррекция частных событий выполняется с учетом условий выхода
алгоритмического процесса за вершину соединения параллельных ветвей.
      Исходя из основных положений языка ГСАП алгоритм построения
детерминированной ПТП для управляющего автомата, заданного на языке
ГСАП, будет включать следующие этапы:
      1) Построение недетерминированной ПТП управляющего автомата,
состоящей из совокупности отдельных детерминированных ПТП для всех
частных событий, реализуемых в параллельных ветвях и последовательной
части алгоритма управления. Построение таких ПТП выполняется также как
и для обычных ГСА без учета связи между отдельными ветвями.
      2) Выполнение коррекции всех частных событий, полученных на
предыдущем этапе, в соответствии с заданными условиями выхода
алгоритмического процесса за вершину объединения параллельных ветвей. В
результате получим общую скорректированную недетерминированную ПТП
управляющего автомата.
      3) Выполнение детерминизации недетерминированной ПТП,
полученной на предыдущем этапе на основе алгоритма детерминизации,
предложенного в главе 2.
      П р и м е р 4.8. Для управляющего автомата, заданного на языке ГСАП
(рис. 4.6), построить недетерминированную и детерминированную ПТП и
соответствующие им СКУ автомата Мура при условии, что выход
алгоритмического процесса за вершину объединения параллельных ветвей
осуществляется после окончания алгоритмических процессов во всех ветвях,
но не обязательно одновременно. Для заданной исходной ГСАП для
                                                                       102