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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

78
Выполнив описание выражения (4.28) в исчислении предикатов,
получим:
]].σ)σ(&δ)δ(&
&δ)[δ(&τ)τ(&)(τ)[τ()(
)()(
)(
11
11
1
1
ee
e
i
t
j
t
tS
(4.29)
Если не пользоваться скобками, определяющими область действия
кванторов существования, считая при этом, что действие квантора
распространяется на всю конъюнкцию предикатов, расположенных правее
квантора, и учесть (4.20), то выражение (4.29) примет вид:
).1δ(&δ)δ(&
&)(δ)δ(&τ)τ(&τ)τ()(
011
11
)(
)
(
1
1
S
tS
e
e
i
t
i
t
(4.30)
Обозначив на основании (4.24) связную группу предикатов
)1δ(&δ)(&)(δ)δ(
011
)
(
1
S
e
i
через
1
1
S
, получим следующую форму записи выражения (4.30):
)1τ(&τ)τ(&)(τ)τ()(
111
)
(
1
StS
e
t
i
t
. (4.31)
Из (4.31) следует, что описание выражения
ji
zzS
, также как и
описание выражения
i
zS
, состоит из аналогичных трех частей.
Описание события S, заданное регулярным выражением алгебры
событий
i
z
, т.е.
i
zS
.
На основании правила развертывания итерации, закона
коммутативности для итерации и закона нейтральности пустого слова
исходное выражение в алгебре событий может быть переписано в следующей
эквивалентной форме:
e
e
ii
zzS
. (4.32)
Учитывая исходную формулу описываемого выражения, можно (4.32)
переписать и так:
e
e
i
SzS
. (4.33)
Выполнив описание выражения (4.33) формулами исчисления
предикатов, получим:
)1τ(&τ)τ(&)(τ)τ()()(
)
(
110
1
StStS
e
t
i
t
. (4.34)
Описание дополнения
S
события S. 
      Выполнив описание выражения (4.28) в исчислении предикатов,
получим:
            S (t )  (τ)[ j (τ) & ( τ1 )e( τ1 ) & (δ)[ i δ  &
                           t                     1 t                      
                                                                                        (4.29)
                             & ( δ1 )e(δ1 ) & (σ)e(σ)]].
                                     1                       

      Если не пользоваться скобками, определяющими область действия
кванторов существования, считая при этом, что действие квантора
распространяется на всю конъюнкцию предикатов, расположенных правее
квантора, и учесть (4.20), то выражение (4.29) примет вид:
            S (t )  (τ) i τ  & ( τ1 )e( τ1 ) & (δ) i (δ) &
                     t                     1 t                     
                                                                                        (4.30)
                       & ( δ1 )e(δ1 ) & S 0 (δ  1).
                                 1  

        Обозначив на основании (4.24) связную группу предикатов
                      (δ) i (δ) & ( 1 )e(δ1 ) & S 0 (δ  1)
                                                    1  

через S1   1 , получим следующую форму записи выражения (4.30):
                 S (t )  (τ) i (τ) & ( τ1 )e( τ1 ) & S1 ( τ  1) .                  (4.31)
                            t                    1 t

      Из (4.31) следует, что описание выражения S  zi z j , также как и
описание выражения S  zi , состоит из аналогичных трех частей.

      Описание события S, заданное регулярным выражением алгебры
событий zi  , т.е.
                                                        S  zi .
      На    основании     правила       развертывания итерации,   закона
коммутативности для итерации и закона нейтральности пустого слова
исходное выражение в алгебре событий может быть переписано в следующей
эквивалентной форме:
                         S  e  zi zi e.                 (4.32)
      Учитывая исходную формулу описываемого выражения, можно (4.32)
переписать и так:
                       S  e  Sz i e.                 (4.33)
      Выполнив описание выражения (4.33) формулами                                    исчисления
предикатов, получим:
           S (t )  S 0 (t )  (τ) i (τ) & ( τ1 )e( τ1 ) & S ( τ  1) .              (4.34)
                                     t                    1 t



        Описание дополнения S события S.

                                                                                                 78

Страницы