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

                   S 1 (t  1)  x1 S 0  x1 x 4 S 3  x1 x2 x 3 S1;
                   S 2 (t  1)  S 5 ;
                   S 3 (t  1)  x1 x2 S1  x1 x 2 S 0 ;
                                                                                                    (3.9)
                   S 4 (t  1)  x 2 x4 S 2  x1 x4 S 3 ;
                   S 5 (t  1)  x1 x2 S 0  x2 x 4 S 2  x 2 x4 S 4  x1 x2 x3 S1;
                   S 6 (t  1)  x 4 S 2  x 2 S 1  x1 S 3  ( x 2  x 4) S 4 .
        Распределение сдвигов для заданной СКУ:
              0  [];                   4  ~
                                                x 4;
                1  ~x 1;                                      5  ~
                                                                        x 2, ~
                                                                             x 3 ;        (3.10)
                 2  ~
                       x1 , ~
                            x2 , ~
                                 x3 , ~
                                      x4 ;                       6  [].
                  ~
                   3   x ,~ x , ~ ;
                            1   2   x4
        Произведем поочередной анализ событий исходной СКУ (3.9):
        1) Событие S1 состоит из трех ветвей:
                               S1 t  1  x1 S 0 .
                                1
        а)        Ветвь                              Для                     этой   ветви    имеем:
    1
[ X 1]  [ 0 ]  [ x1]  []   . Поэтому запись                         этой ветви остается без
изменения.
                                 S 1 t  1  x1 x4 S 3 .
                                   2
         б)       Ветвь                                              Для        этой    ветви       имеем:
[ X 12]  [ 3 ]  [ x1 , x4 ] ,      X 1  3   x1 x4 .
                                         2

                                                                               1, 2
        Для события S3 находим [ X 13]  [ X 32]  [ x1] , X 3  x1 .
      Откуда [ X 12  3 ]  [ X 13,2]    , X 1  3  & X 13, 2  0 , поэтому X 12  0 и
                                                                 2

 2
S1  0 .
                                  S1 t  1  x1 x 2 x3 S1
                                        3
         в)      Ветвь                                               Для         этой   ветви       имеем:
[ X 13]  [1 ]  [ x1] ,       X 1 1   x1 .
                                  3


        Для события S1 находим [ X 11]  [ X 12]  [ X 13]  [ x1] ,             1, 2, 3
                                                                               X 3  x1 . Откуда
[ X 13 1 ]  [ X 13, 2,3]  [] , X 13 1  & X 13, 2,3  x , поэтому новая запись входного
сигнала для события S13 будет иметь вид X 13  x 2 x3 .
     2) Событие S2 имеет одну ветвь, для которой X 12  1 , поэтому
дальнейший анализ не производится.
     3) Событие S3 состоит из двух ветвей:
                                    S 3 t  1  x1 x 2 S 1 .
                                        1
        а)        Ветвь                                              Для        этой    ветви       имеем:
[ X 13]  [1 ]  [ x1] ,       X 3 1   x1 .
                                    1

                                                                                 1, 2 ,3
        Для         события                 S1   в      п.1,в        получено  X 1  x1    Откуда
[ X 13 1 ]  [ X 13, 2,3]  [],          X 3 1  & X 1  0 , поэтому X 3  0 и ветвь S 3  0 .
                                               1           1, 2 ,3           1              1



                                                                                                            58