Другие предметы \ Схемотехника ЭВМ

Cети Петри. Структура СП. Гибкий производственный модуль. Алгоритм преобразования в ординарную СП, страница 4

Множество достижимости R(C,m0) -  это множество всех маркировок, достижимых в СП из начального множества m0.

 


                t1                              p4

p2

t2           t4                       (**)

p1

t3            p3

t5

                     m0=(1,0,0,0)

t1      t2          t3

(0,1,0,0)      (0,1,1,0)         (0,0,1,0)

            t4            t4                тупиковая     маркировка

(0,0,1,0)      (0,0,2,0)

 


тупиковая                 t5

         маркировка                (0,0,0,1)

t6

(1,0,0,0)

            Классификация СП по динамическим свойствам

1.Безопасная СП - это маркированная СП, в которой число маркеров в любой позиции pk P никогда не превышает 1. В следующем примере приведена СП, которая будет безопасной при начальной маркировке m0=(1,0,0,0). Если m0=(1,0,0,1), то СП уже не будет безопасной.

           t1      p2      t3

 

p1                             p4    t5         (11a)

            t2       p3     t4  

2.k-ограниченная СП - это маркированная СП, в которой каждая маркировка не превосходит числа k:

k = max   max  ( m(pk))

                          pkÎP    mÎR(C,m0)

Замечание:1-ограниченная СП - это безопасная СП.

Ограниченная СП - это маркированная СП, в которой для любой позиции pkÎP можно найти такое k< ¥, для которой она является k-ограниченной.

Пример неограниченной СП для m0=(1,2,0), где неограниченной является позиция p2:

t1            p2               t3

 

p1                          t2              p3      (*)

t4

3.Строго сохраняющаяся СП - это маркированная СП, в которой в процессе функционирования общее число маркеров остается постоянным:

S m0(pi) =  S m(pi)

piÎP           piΠ

m Î R(C,m0)

                                      t2    Пример строго

                                            сохраняющейся СП:

p1                         p3     

t1                         m0=(1,0,1,0)

 n

p2                              p4         S m(pi)=2=const

t3     i=1

 

Пример не строго

p1                   p3                   сохраняющейся СП:

                                           m0=(0,0,1)

t1             t2             3 

p2                                       S  m0(pi)=1

i=1

m0 [t2 > m`=(1,1,0)

3

S  m`(pi)=2

i=1

 

 

Сохраняющаяся СП - это СП, для которой существует положительный ненулевой вектор W>0 такой, что для него выполняется равенство:

S  wim0(pi) = S  wim(pi),

piÎP               piÎP

m Î R(C,m0).

Замечание: Если вектор W - единичный, то СП является строго сохраняющейся.         

p1                   p3       Пример сохраняющейся     сети:

m0=(1,0,1,0,1)

t1             p5     t3                5

S  wim(pi)=3=const

p2               p4                i=1

при W=(1,2,1,2,1)

t2             t4   

     p1                            p4     Пример несохраняющейся

сети:

t1      p3        t3           m0=(1,0,0,1,0)   S=2

                                               ¯  t1

          p2                p5           m1=(0,1,0,1,0)   S=2

¯ t2

t2                t5           m2=(1,0,1,1,0)   S=3

¯  t3

...

Живая СП - это маркированная СП, в которой для каждого перехода ti при любой маркировке m, достижимой из m0, можно получить с помощью совокупности отношений непосредственного следования маркировку mi,при которой переход будет разрешен.

               t1   p2     t3                          Пример

живой сети:

p5      t5 (00011) ® t5

p1                      p4               (10010) ® t1 

t2     p3                              (01010) ® t3

t4               (00001) ® t5  

(10000) ®t2

и т.д.

Теорема 1: Алгоритм преобразования СП в ординарную СП без петель сохраняет основные свойства исходной сети: ограниченность, сохраняемость и живость.

           Динамические свойства автоматной СП

Из определения автоматной сети Петри вытекают следующие свойства такой СП:

Скачать файл