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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

87
).1τ(&)τ(&)τ()τ(&)(τ&)(τ)τ()(
),ε()ε(&)(ε)ε()(
),1η(&)η()η(&)(η&)(η)η()(
)],1δ()1δ([&
&δ)δ(&)(δ&)(δ)δ()(
),1τ(&)τ()τ(&)(τ&)(τ)τ()(
,)(
1171016,36
2
0,1
1510
1
3,1
1
3,11415,35
1
2,1
1
0,1
1
2,1
114,22
1
1,1
1
1,114,114,22
1
0,1
2
0,1
1
0,11
1
1
1
1
1
)(
SxxxtS
xStS
SxtS
SS
xtS
SxtS
SStS
t
t
t
t
e
ee
ee
ee
(4.53)
Выполняя спуск кванторов в уравнениях системы (4.53) на основании
аксиом (4.44) и (4.45), получим следующую систему беcкванторных
канонических уравнений, которая имеет вид:
.&&1&&
,,1&
,1&1&&
,1&
11&&
,1&1&&
,
,
2
0,170
1
0,16,36
2
0,1
1
3,10
1
3,150
1
3,1
1
2,1
1
3,15,35
1
2,1
1
1,14
1
0,1
1
2,14,22
1
1,1
1
0,14,1
1
1,14,22
1
0,1
2
0,1
1
0,11
700
StxtxtStetxtS
StStStxtStS
tStetStetxtS
tSte
tStStetxtS
tStetStetxtS
SStS
txtxtS
(4.54)
Для наглядности при проверке правильности формального
представленных событий можно использовать графы НДА, реализующие эти
события. Для нашего примера граф НДА, построенный на основе системы
(4.54) и реализующего событие
S
1
, имеет вид (рис.4.2).
1
3,10
SS
70
xx
5
x
1
2,1
S
5,35
& ex
4
e
1
1,1
S
4,22
& ex
4
e
1
0,1
S
4,22
& ex
4,1
e
2
0,1
S
6,36
& ex
7
0
& xx
4,22
& ex
1
y
2
y
           S1 (t )  S11,0  S12,0 ,

       S11,0 (t )  (τ) x2 (τ) & e2, 4 (τ) & ( τ1 )e1, 4 ( τ1 ) & S11,1 (τ  1),
                       t                                 1 t

       S11,1 (t )  (δ) x2 (δ) & e2,4 (δ) & ( δ1 )e(δ1 ) &
                                                       1  

                   & [ S11, 2 (δ  1)  S11,0 (δ  1)],                                                          (4.53)

       S11,2 (t )  (η) x5 (η) & e3,5 (η) & ( η1 )e4 (η1 ) & S11,3 (η  1),
                                                       1 

       S11,3 (t )  ( ε ) S 0 (ε) & ( ε1 ) x5 (ε1 ),
                                           1 

       S12,0 (t )  (τ) x6 (τ) & e3,6 (τ) & ( τ1 ) x0 ( τ1 ) & x7 ( τ1 ) & S1 ( τ  1).
                       t                               1 t

      Выполняя спуск кванторов в уравнениях системы (4.53) на основании
аксиом (4.44) и (4.45), получим следующую систему беcкванторных
канонических уравнений, которая имеет вид:
      S 0 t   x0 t   x7 t ,
       S1 t   S11,0  S12,0 ,
       S11,0 t   x2 t  & e2, 4 t  & S11,1 t  1  e1,4 t  & S11,0 t  1,
                                                
       S11,1 t   x2 t  & e2, 4 t  & S11,2 t  1  S11,0 t  1       
                                                                                                                 (4.54)
        e4 t  & S11,1 t  1,
       S11, 2 t   x5 t  & e3,5 t  & S11,3 t  1  et  & S11, 2 t  1,
       S11,3 t   S 0 t   x5 t  & S11,3 t  1,                S0 t   S11,3 ,
       S12,0 t   x6 t  & e3,6 t  & S11,0 t  1  x0 t  & x7 t  & S12,0 .
        Для наглядности при проверке правильности формального
представленных событий можно использовать графы НДА, реализующие эти
события. Для нашего примера граф НДА, построенный на основе системы
(4.54) и реализующего событие S 1 , имеет вид (рис.4.2).

              x5                   e4                        e4                     e1, 4                x0 & x7
 x0  x7              x5 & e3,5               x2 & e2,4               x2 & e2,4              x6 & e3,6
               1                       1                        1                     1
           SS0 1, 3                S   1, 2                  S  1,1                 S 1, 0               S12,0

                                                                                        y1                  y2
                                                                      x2 & e2, 4



                                                                                                                          87

Страницы