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

      2) Полученные конъюнкции am(t)&X(am,as)(t) объединяют знаком
дизъюнкции. Такую операцию выполняют для всех полных событий
(состояний).
      3) Все полные события (состояния), представленные в левой части
уравнений СКУ, отмечаются соответствующими сочетаниями выходных
сигналов.
      П р и м е р 2.1. Сформировать полные входные сигналы для одного из
шагов алгоритма работы ДА.
      Пусть на данном шаге алгоритма работы автомата заданы следующие
два подмножества частных входных сигналов.

                            [ X ] 1  [ x1 x3 , x1 x2 , x3 , x3 ] ,
                        [ X ] 2  [ x1 , x1] .
      В соответствии с п.2 алгоритма детерминизации получим следующие
сочетания частных входных сигналов в подмножестве  X 1 :
                    [ x1 x3 , x1 x2 x3 , x1 x2 x3 , x1 x2 , x3 , x3 ]
      Из анализа полученных сочетаний частных входных сигналов следует,
что в данном сочетании имеет место:
          сочетания, которые не являются выводимыми ни из какого
одного из сочетаний подмножества  X  1 . Для нашего примера к таким
сочетаниям относятся: x1 x3 , x1 x2 x3 , x1 x2 x3 ; такие сочетания остаются для
дальнейшего рассмотрения;
              сочетание x1 x2 , которое выводимо из сочетаний x1 x2 x3 и x1 x2 x3 .
Так как истинность сочетания x1 x2 всегда влечет истинность одного из двух
сочетаний, из которых выводим частный входной сигнал x1 x2 , то данный
входной сигнал исключается из дальнейшего рассмотрения;
              элементарные сочетания – входной сигнал x3 , выводимый из
сочетания x1 x2 x3 и входной сигнал x3 , выводимый из сочетаний x1 x3 и
x1 x2 x3 . Истинность сигнала x3 еще не означает истинность сочетания
x1 x2 x3 , а истинность сигнала x3 еще не означает всегда истинность хотя бы
одного из сочетаний x1 x3 и x1 x2 x3 . Поэтому сигналы x3 и x3 остаются для
дальнейшего рассмотрения.
       Таким образом, откорректированное подмножество частных входных
сигналов  X 1 будет иметь вид:
                       [ X ] 1  [ x1 x3 , x1 x2 x3 , x1 x2 x3 , x3 , x3 ]
     Сочетания всех частных входных сигналов для двух заданных
подмножеств  X 1 и  X 2 после корректировки подмножества  X  1 будут
представлены следующим множеством:

                                                                                  29