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

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

80
rki
zzzR
. (4.39)
Требуется построить предикатную формулу
tS
i
,
, получающуюся из
(4.38) путем подстановки вместо группы предикатов с переменными в
называющей форме, описывающих левую часть формулы (4.39), группу
предикатов в называющей форме, описывающих правую часть формулы
(4.39). Тогда событие
tS
i
,
запишется так:
)].1τ(&]τ)τ(&)(τ&δτ&δ)δ(&)(δ)δ(
τ&)τ(&)(τ&τ)[[τ()()(
,1111
111,,
)()(
)(
11
1
i
k
t
r
t
t
i
ii
S
ttStS
ee
e
Выполнив необходимые преобразования, в том числе частичное
переименование связанной переменной, окончательно получим:
).1σ(&σ)σ(&)(σ)τ(&τ)τ(&)(τ)τ(
)1τ(&τ)τ(&)(τ)τ()()(
,1111
,111,,
)()(
)(
11
1
i
k
t
r
t
i
t
i
t
ii
S
StStS
ee
e
(4.40)
Обозначив на основании (4.24) связную группу предикатов
)1σ(&σ)σ(&)(σ)σ(
,11
)(
1
i
k
S
e
(4.41)
через
1
1
S
, получим следующую форму записи выражения (4.40):
.1τ&τ)τ(&τ)τ(
)1τ(&τ)τ(&τ)τ()()(
111
,111,,
1
1
)(
S
StStS
e
e
t
r
t
i
t
i
t
ii
(4.42)
Откуда следует, что событие
i
S
,
будет представлено двумя
предикатными формулами, одна из которых (4.42), а другая, определяемая
связной группой предикатов (4.41), после переименования связанной
переменной будет иметь вид:
)1τ(&τ)τ(&)(τ)τ()(
,111
)(
1
i
t
k
t
StS
e
(4.43)
Таким образом, исходя из полученных результатов, справедливо
следующее утверждение:
Любое регулярное выражение алгебры событий
S
, заданное в
алфавите [Z], может быть рекурсивно описано в этом же алфавите системой
A
предикатных формул, полученных из выражений типа (4.37) при помощи
необходимого количества подстановок. При этом любые предикатные
формулы системы имеют одинаковую структуру и представляются в виде
выражений, состоящих из трех частей, как это было показано, например, в
(4.37). 
                                                   R  zi  z k z r .                                            (4.39)

                                                      t  , получающуюся из
                                                  i
        Требуется построить предикатную формулу S ,
(4.38) путем подстановки вместо группы предикатов с переменными в
называющей форме, описывающих левую часть формулы (4.39), группу
предикатов в называющей форме, описывающих правую часть формулы
                            t  запишется так:
                        i
(4.39). Тогда событие S ,
S i , (t )  S i ,1 (t )  (τ)[[ τ  t &  i (τ) & ( τ1 ) & e( τ1 ) 
                                                                       1 t

 (δ) r (δ) & ( δ1 )e(δ1 ) & τ  δ &  k (τ) & ( τ1 )e( τ1 )] & S i , ( τ  1)].
    t                1 t                                                    1 

      Выполнив необходимые преобразования, в том числе частичное
переименование связанной переменной, окончательно получим:
      S i , (t )  S i ,1 (t )  (τ) i (τ) & ( τ1 )e( τ1 ) & S i , ( τ  1) 
                                          t                   1 t
                                                                                                                 (4.40)
 (τ) r (τ) & ( τ1 )e( τ1 ) & ( τ ) k (σ) & ( σ1 )e(σ1 ) &                            S i , (σ    1).
   t                 1 t                                          1  

          Обозначив на основании (4.24) связную группу предикатов
                         (σ) k (σ) & ( σ1 )e(σ1 ) & S i , (σ  1)                                           (4.41)
                                                 1  

через S1   1 , получим следующую форму записи выражения (4.40):
            S i , (t )  S i ,1 (t )  (τ) i τ  & ( τ1 )e( τ1 ) & S i , ( τ  1) 
                                                   t                 1 t
                                                                                                                 (4.42)
             (τ) r τ  & ( τ1 )eτ1  & S1 τ  1.
                 t                     1 t
                                      i
      Откуда следует, что событие S ,   будет представлено двумя
предикатными формулами, одна из которых (4.42), а другая, определяемая
связной группой предикатов (4.41), после переименования связанной
переменной будет иметь вид:
                   S1 (t )  (τ) k (τ) & ( τ1 )e( τ1 ) & S i , ( τ  1)                                     (4.43)
                                  t                      1 t

      Таким образом, исходя из полученных результатов, справедливо
следующее утверждение:
      Любое регулярное выражение алгебры событий S  , заданное в
алфавите [Z], может быть рекурсивно описано в этом же алфавите системой
 A  предикатных формул, полученных из выражений типа (4.37) при помощи
необходимого количества подстановок. При этом любые предикатные
формулы системы имеют одинаковую структуру и представляются в виде
выражений, состоящих из трех частей, как это было показано, например, в
(4.37).

                                                                                                                          80

Страницы