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

Суммирование СКУ. Эта операция сводится к получению из двух или более
СКУ общей СКУ с целью построения нового автомата, который будет
эквивалентен двум или более параллельно работающим автоматам,
построенным по исходным СКУ. Таким образом, операция суммирования в
структурной интерпретации эквивалентна замене параллельного соединения
нескольких автоматов одним автоматом. При этом, если каждый из исходных
автоматов представлен детерминированной СКУ, то в результате операции
суммирования будет получена недетерминированная СКУ, так как в
объединенной СКУ будет объединено несколько начальных событий в одно
событие.
Для выполнения операции суммирования с последующей детерминизацией
объединенной СКУ необходимо:
             переобозначить события (состояния) исходных СКУ, например, введением для событий
дополнительного верхнего индекса, указывающего на принадлежность события к СКУ с номером i, где
i  1, l , l   - число исходных автоматов;
             образовать новую объединенную СКУ путем объединения уравнений всех исходных СКУ в
одну группу;
             образовать начальное     событие для результирующей объединенной СКУ путем
объединения множеств начальных событий исходных СКУ в группу (совокупность), представляющую
собой конъюнкцию начальных событий исходных СКУ;
               выполнить детерминизацию объединенной СКУ, если это необходимо для дальнейшего
синтеза объединенного автомата.
Для варианта суммирования СКУ, когда исходные автоматы заданы в детерминированной форме, при
выполнении операции детерминизации объединенной СКУ будут возникать сочетания из l событий
(состояний). В каждое такое сочетание из l событий будут входить только по одному из событий
(состояний) каждой из исходных детерминированных СКУ, а общее число таких сочетаний, полных
событий, объединенной детерминированной СКУ будет не более величины M  M 1... M i ... M l , где
M i - число событий (состояний) i-го автомата. В том случае, если в каждом из автоматов все состояния, в
том числе и начальное достижимы из любого состояния, то общее число полных событий объединенной
детерминированной СКУ будет равно М. Тогда для рассматриваемого варианта исходных автоматов все
сочетания из обозначений событий (состояний), входящих в исходные СКУ, можно заранее перечислить,
т.е. в этом случае для решения задачи определения всех возможных сочетаний событий, одновременное
существование которых в объединенном автомате возможно, не потребуется использование алгоритма
детерминизации, рассмотренного ранее. В то же время описание полных событий детерминированной СКУ
объединенного автомата можно получить в этом случае путем выполнения операции конъюнкции правых
частей тех уравнений исходных СКУ, формализующих события, сокращенные обозначения которых входят
в рассматриваемое полное событие.
В том случае, если в исходных детерминированных СКУ не удовлетворяются условия достижимости
состояний, указанные выше или если исходные СКУ заданы в недетерминированной форме, то
детерминизацию объединенной СКУ можно выполнить только с использованием алгоритма
детерминизации, рассмотренного в главе 2.
Получение СВФ объединенного автомата выполняется по разному в зависимости от того, одинаковый или
разный смысл имеют выходные сигналы объединяемых автоматов. Если все автоматы работают на один и
тот же операционный автомат, то все сигналы имеют одинаковый смысл и СВФ объединенного автомата
получают следующим образом. Осуществляют дизъюнкцию правых частей уравнений СВФ объединяемых
автоматов для одинаковых выходных сигналов. Далее, если необходимо выразить уравнения СВФ через
полные события, то процедура их построения будет та же, что была рассмотрена в главе 2.
Если же действие одинаково обозначенных выходных сигналов в разных автоматах на операционный
автомат разное, то необходимо выходные сигналы в исходных уравнениях СВФ переобозначить, например,
путем введения верхних индексов.
Конкатенация СКУ. Конкатенация двух СКУ позволяет получить автомат, последовательно реализующий
два алгоритма. Для выполнения такой операции необходимо отождествить конечное событие первой СКУ
S k ,1 с начальным событием второй S 0, 2 . Под конечным событием здесь понимается событие первой СКУ,

                                                                                                    143