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

                      Рис.4.2. Граф НДА, реализующего событие S 1

      В заключение рассмотрим представление события S 1 на языке РВАС
и построение на его основе системы канонических уравнений. Для этого
воспользуемся временными схемами формирования события S 1 (рис.4.1), на
основании которого событие S 1 на языке РВАС может быть представлено
следующим выражением:
       S1  S 0 {x5 }( x5e3,5 ){e4 }( x2 e2, 4 ){e4 }( x2 e2, 4 ){e1, 4 }
                                                                          (4.55)
      {( x2 e2,4 ){e4 }( x2 e2, 4 ){e1,4 }  ( x6 e3,6 ){( x0 x7 )}}
         Выполнив в выражении (4.55) раскрытие итерационных скобок, в
которых представлено описание условия сохранения события S 1 , и
некоторые предварительные преобразования, получим описание события S 1
в следующем виде:
   S1  [ S 0 {x5 }( x5 e3,5 ){e4 }( x2 e2,4 )  S1 ( x2 e2, 4 ){e4 }]( x2 e2, 4 ){e1, 4 } 

   S1 ( x6 e3,6 ){( x0 x7 )}  S11,0  S12,0 .                                      (4.56)


      Полученное регулярное выражение (4.56) на основании методики,
представленной в п. 4.1.2, преобразуется в следующую каноническую
систему регулярных выражений для всех событий, реализуемых в исходном
алгоритме для события S 1 :

         S11,0  S11,1 ( x 2 e2, 4){e1, 4}  S 11,1 ( x2 e2, 4)  S11,0 e1, 4 ,
         S 11,1  S11,2 ( x2 e2, 4){e4}  S1 ( x2 e2, 4){e4}  ( S11, 2  S1) e4 ,
         S 11,2  S 0{x5 }( x5 e3,5){e4}  S11,3 ( x5 e3,5){e4} 
                                                                                     (5.57)
                 S11,3 ( x5 3,5)
                            e          S11, 2   e4 ,
         S11,3  S 0{x5 }  S 0  S 1,3 x5 ,             S 0  S11,3 ,
       S12,0  S1 ( x6 e3,6){( x0 x7 )}  S1 ( x6 e3,6)  S12,0{( x0 x7 )}.
      Система уравнений (4.57) полностью соответствует канонической
системе уравнений (4.54), полученной по описанию события S 1 на языке
исчисления предикатов.
                  4.3. Язык граф-схем алгоритмов (ГСА)
                            4.3.1. Общие сведения о языке ГСА
     Граф-схемы алгоритмов нашли широкое применение для описания
функционирования управляющих микропрограммных устройств в различных
отраслях техники, в том числе и в вычислительной технике. Это объясняется
их хорошей обозримостью, наглядностью и простотой конструкции, а также

                                                                                              88