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

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


                   5.4. Контроль правильности построения
                        функций возбуждения элементов
                             памяти систем МПУ
В связи с тем, что операции детерминизации и кодирования НДА являются
обратными друг другу, то этим обстоятельством можно воспользоваться для
организации контроля правильности построения функций возбуждения
элементов памяти систем МПУ. Такая процедура может быть организована
на основе выполнения операции детерминизации НД СКУ для Q-событий,
полученной в результате кодирования, с последующей минимизацией
выражений для исходных событий, представляющих управляющий алгоритм.
Если после детерминизации системы уравнений для Q-событий получим
СКУ, которая будет соответствовать исходной СКУ до ее кодирования, то


                                                                                                144