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

        [ X ] 1, 2  [ x1 x3 , x1 x3 , x1 x2 x3 , x1 x2 x3 , x1 x3 , x1 x3 , x3 , x3 , x1 , x1 ]
     В соответствии с п.5а и 5б алгоритма детерминизации из полученного
множества сочетаний частных входных сигналов остаются для дальнейшего
рассмотрения следующие шесть сочетаний:
                 [ x1 x3 , x1 x3 , x1 x2 x3 , x1 x 2 x3 , x1 x3 , x1 x3 ]
      К двум последним сочетаниям частных входных сигналов в
соответствии с п.5в алгоритма детерминизации необходимо применить
операцию развертывания, так как каждое из них является выводимым из
другого сочетания рассматриваемого множества и их истинность не влечет
истинность сочетаний, из которых они выводимы. Для нашего примера
сочетание x1 x3 выводимо из сочетания x1 x2 x3 , а сочетание x1 x3 выводимо
из сочетания x1 x2 x3 . Операции развертывания будут иметь вид:
                            x1 x3 ( x2  x2 ) и x1 x3 ( x2  x2 )
     В результате имеем после учета эквивалентных, ранее полученных
сигналов, следующие полные входные сигналы, которые действуют на
данном шаге алгоритма работы ДА:
              [ x1 x3 , x1 x3 , x1 x2 x3 , x1 x2 x3 , x1 ( x2) x3 , x1 ( x2) x3 ]
где переменная в скобках свидетельствует о применении операции
развертывания.
      П р и м е р 2.2. Сформировать полные входные сигналы для одного из
шагов алгоритма работы ДА, когда на данном шаге алгоритма работы
автомата заданы два подмножества частных входных сигналов, одно из
которых не удовлетворяет условиям полноты.
                            [ X ] 1  [ x2 , x2 , x1 x2]
                                     [ X ] 2  [ x3 , x 2 x 3 ]
     Операции определения сочетаний частных входных сигналов в
заданных подмножествах новых частных входных сигналов не дает, поэтому
в соответствии с п.2в алгоритма детерминизации выполняем проверку
заданных подмножеств на полноту состава входных сигналов. Из двух
подмножеств второе подмножество  X  2 не удовлетворяет условиям
полноты, так как дизъюнкция входных сигналов не равна единице:
                            x 3  x 2 x 3  x3  x 2 .
      Запрещенный входной сигнал для подмножества  X  2 , определяемый
как отрицание от дизъюнкции входных сигналов, имеет вид:
                                          x3  x2  x 2 x3
     Таким образом, скорректированные подмножества частных входных
сигналов примут следующий вид:



                                                                                                   30