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

соответствующие события перехода будут неопределенными. Запрещенные
входные сигналы определятся из выражения, представляющего собой
отрицание от дизъюнкции всех частных входных сигналов рассматриваемого
подмножества.
      4) Для всех откорректированных подмножеств частных входных
сигналов, действующих на данном шаге алгоритма работы ДА Мура,
находится множество всех не эквивалентные между собой и не
эквивалентные нулю сочетания частных входных сигналов.
      5) Выполняется анализ и корректировка полученного множества
сочетаний частных входных сигналов, действующих на данном переходе ДА
Мура, на основании которого:
      а) оставляют для дальнейшего рассмотрения и записываются в третий
столбец ПТП ДА сочетания, не являющиеся выводимыми ни из какого
одного из сочетаний рассматриваемого множества и те из выводимых, для
которых их истинность не влечет истинность хотя бы одного из сочетаний, из
которого это сочетание само выводимо;
      б) исключают из дальнейшего рассмотрения те из выводимых
сочетаний, истинность которых влечет истинность хотя бы одного из
сочетаний, из которых они выводимы;
      в) к оставленным выводимым сочетаниям применяют операцию
развертывания, умножая их на выражение вида  xi  xi x j  x j , где
xi ,, x j — элементарные входные сигналы, которые не вошли в выводимое
сочетание элементарных входных сигналов по сравнению с сочетанием, из
которого они выводятся. Такая операция необходима для обеспечения
условий однозначности на рассматриваемом переходе ДА (шаге алгоритма).
Из полученных в результате выполнения операции развертывания частных
входных сигналов удаляются те из них, которые эквивалентны ранее
полученным. В том случае, если выводимое сочетание частных входных
сигналов выводимо из нескольких сочетаний частных входных сигналов, то
при операции развертывания необходимо использовать те элементарные
входные сигналы xi ,, x j , которые входят в сочетание с наибольшим числом
букв.
       В результате выполнения п.5 алгоритма детерминизации будут
получены все полные входные сигналы X (a m , a S ) , действующие на
рассматриваемом шаге работы алгоритма ДА.
      Примечание: в том случае, если детерминизация НДА используется только с
целью определения состава всех полных событий, то операцию развертывания к
выводимым сочетаниям частных входных сигналов можно не применять, так как новых
полных событий не получим. Для таких входных сигналов в столбце 4 будем ставить
дополнительно знак ( ).
      6) Для каждого полного входного сигнала X (a m , a S ) , записанного в
третьем столбце, определяют, используя исходную ПТП НДА, совокупность
(сочетание) частных событий, которые выводимы из каждого исходного
                                                                             27