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

     Дополнение S события S в исчислении предикатов описывается
обычным образом на основании правил исчисления предикатов. Так, если
          S (t )  (τ) j (τ) & ( τ1 )e(τ) & S1 (τ  1) , то
                              t               1 t

                   S (t )  (τ)[ j (τ)  ( τ1 )e( τ1 )  S1 ( τ  1)] .                  (4.35)
                              t                  1 t


       Описание      регулярных     выражений     алгебры       событий
произвольной формы формулами исчисления предикатов.
       В разделе 4.1.2 было показано, что любое РВАС, заданное
произведением элементарных одноэлементных событий может быть
представлено в виде системы регулярных выражений (4.12), в которой любое
входящее в систему регулярное выражение, представляется произведением
двух переменных:
                                      S i ,  S i ,1 z p ,                             (4.36)
где   S i ,1        -     сокращенное                  обозначение        события,   являющегося
                                                          i
               непосредственно предшествующим событию S ,  , а zp -
               буква входного алфавита [Z].
      Выражения типа (4.36) на основании предыдущих результатов могут
быть представлены формулами исчисления предикатов в следующем виде:
                  S i , (t )  (τ) p (τ) & ( τ1 )e( τ1 ) & S i ,1 ( τ  1) .        (4.37)
                                t                1 t

      На основании полученных в разделе 4.2 результатов, можно
сформулировать следующее предложение:
      Любое регулярное выражение алгебры событий, заданное произведением
элементарных одноэлементных событий z1, z2 ,..., z F может быть описано в
алфавите [Z] системой одноместных формул исчисления предикатов первого
порядка с ограниченными кванторами вида (4.37), общее число формул
системы определяется числом букв входного алфавита [Z], входящих в
исходное произведение [22].
      В том случае, когда в исходном выражении для произведения
элементарных одноэлементных событий (4.11) была выполнена замена,
например, вида z p  R, то используя правила развертывания итерации и на
основании (4.34) получим:
        S i , (t )  S i ,1 (t )  (τ) R(τ) & ( τ1 ) & S i , ( τ  1) ,            (4.38)
                                         t                  1 t

где R – любое регулярное выражение алгебры событий.
       В том случае, когда выражение для R представлено не в виде одной
буквы, то используют операции подстановок, позволяющие получить
описания событий, заданных произвольными регулярными выражениями
алгебры событий. Например, пусть
                                                                                                     79