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

                                       [ X ] 1  [ x2 , x2 , x1 x 2]
                                                                        *
                             [ X ] 2  [ x3 , x2 x3 , ( x2 x3) ]
     Сочетания всех частных входных сигналов для откорректированных
подмножеств  X 1 и  X 2 будут представлены следующим множеством:

   X 1, 2  [ x2   x3 , x2 x3 , x1 x2 x3 , x2 x3 , x1 x2 x3 , x1 x 2 , ( x2 x3)* , x2 , x2 , x3 ] .
      После удаления выводимых сочетаний, истинность которых всегда
влечет истинность одного из сочетаний, из которых эти сочетания выводимы,
для дальнейшего рассмотрения остаются следующие шесть сочетаний:
                [ x2 x3 , x2 x3 , x1 x2 x3 , x2 x3 , x1 x2 x3 , ( x2 x3)*] .
     После применения к первым двум выводимым сочетаниям частных
входных сигналов операции развертывания получим следующие полные
входные сигналы, действующие на данном шаге алгоритма работы ДА:
                     [( x1) x2 x3 , ( x1) x2 x3 , x1 x2 x3 , x 2 x3 , x1 x2 x3 , ( x2 x3)*] .


2.2. Пример детерминизации НДА с построением СКУ и
          СВФ для автоматов Мура и Мили
      В качестве примера детерминизации используется НДА Мура,
заданный графом (рис.1.1). В результате детерминизации необходимо
получить:
      — прямую таблицу переходов ДА Мура, эквивалентного заданному
НДА;
      — системы канонических уравнений ДА Мура и ДА Мили;
      — системы выходных функций (СВФ) ДА Мура и ДА Мили.
      а) По графу НДА Мура (рис. 1.1) строим прямую таблицу переходов
исходного НДА (ПТП НДА) Мура, которая будет иметь вид (табл. 2.1), где
                                           *
для запрещенного входного сигнала  x2 x3  принято событие перехода S4. В
нашем примере при построении ПТП ДА событие, принятое в качестве
неопределенного будем заключать в скобки, то есть имеем: S (  )  (S 4) .




                                                                                                        31