Warning: session_start(): open(C:\Windows\temp\sess_85g7mbj0aaddqstjdsb8h4um15, O_RDWR) failed: No space left on device (28) in C:\www\lemma4.1php\login.php on line 15 Warning: session_commit(): open(C:\Windows\temp\sess_85g7mbj0aaddqstjdsb8h4um15, O_RDWR) failed: No space left on device (28) in C:\www\lemma4.1php\login.php on line 36 Warning: session_commit(): Failed to write session data (files). Please verify that the current setting of session.save_path is correct (C:\Windows\temp) in C:\www\lemma4.1php\login.php on line 36 Сети Петри: модификации и расширения

2.1.4 Представление ЭСС посредством систем переходов

В этом подразделе модель ЭСС сводится к модели систем переходов, которая позволяет представлять и изучать понятия состояний и смены состояний более адекватным образом.

Определение 20    Четверка TS=(S,A,,s0) называется системой переходов, если

  • S — множество  состояний;
  • A — множество  действий (реализаций событий);
  • S×A×Sотношение  перехода;
  • s0 — начальное состояние.

Графический пример системы переходов TS=(S,A,,s0) показан на рис. 2.8, где S={s0,s1,s2,s3,s4}, A={a,b,c} и {(so,a,s1), (so,a,s2), (s1,b,s3), (s2,c,s4)}.

Для изучения ЭСС в контексте систем переходов будет полезно ввести понятие расширенной системы переходов, полученной за счет добавления некоторой структуры в понятие системы переходов.

Определение 21  Расширенная система переходов — это шестерка  TS=(B,E,S,A,,s0),  где:

  • B — множество условий;
  • E — множество событий  (BE=);
  • SP(B)  и  AP(E);
  • (S,A,,s0)система переходов.

Таким образом, расширенная система переходов — это система переходов, состояния которой представляют собой подмножеста условий, а действия — подмножества событий. Далее расширенную систему переходов будем называть просто системой переходов. Справедливость следующей теоремы очевидна.

Теорема 9   Пусть  N=(B,E,F,cin)ЭСС. Тогда  TSN=(B,E,C,U,N,cin)  является системой переходов.

Далее, пусть TSN=(B,E,CN,UN,N,cin) обозначает систему переходов, соответствующую ЭСС N=(B,E,F,cin).

Пусть TS=(B,E,S,A,,s0) — система переходов и (s,a,s'). Тогда можно сказать, что (s\s') — условия, которые перестают выполняться, а (s'\s) — условия, которые начинают выполняться в результате выполнения действия, обеспечивающего смену состояния s на состояние s'. В общем случае различные реализации одного и того же события могут приводить к различным последствиям. Например, в системе переходов, приведенной на рис. 2.9, одна реализация события e1 в состоянии b1 приводит к состоянию {b2}, а другая — к состоянию {b3}. Такая ситуация невозможна в системах переходов, соответствующих ЭСС.

Теорема 10  Пусть  TSN=(B,E,CN,UN,N,cin)система переходов, соответствующая ЭСС  N=(B,E,F,cin). Тогда:

а)  eE    (c1,e,c2),(c3,e,c4)N(c1\c2,c2\c1)=(c3\c4,c4\c3);

б)  uUN    (c1,u,c2),(c3,u,c4)N(c1\c2,c2\c1)=(c3\c4,c4\c3).

Доказательство.

а) Пусть eE и c,c'CN такие, что (c,e,c')N. Покажем, что c\c'=e и c'\c=e.

Так как (c,e,c')N, то c'=(ce)e. Пусть bc\c'. Тогда bc', и поэтому bcebe). Однако верно bc. Значит, be. Тогда c\c'e.

Теперь пусть be. Поскольку (c,e,c')N, то c[e>, что, в свою очередь, означает ec и ec=. Так как be, то bc. Кроме того, из ec и ec= следует ee=. Значит, be. Поскольку bc и be, то bce. Тогда be и bce означает bc'. Наконец, так как bc, то bc\c', т.е. ec\c'.

Таким образом, имеем c\c'=e. Рассуждая аналогично, можно показать, что c'\c=e.

Теперь предположим (c1,e,c2),(c3,e,c4)N. Также, рассуждая, как выше, получаем c1\c2=e=c3\c4 и c2\c1=e=c4\c3.

б) Пусть (c1,u,c2),(c3,u,c4)N. Тогда, используя пункт а), легко показать, что c1\c2=u=c3\c4 и c2\c1=u=c4\c3. □

Таким образом, в системах переходов, соответствующих ЭСС, смена состояний, вызванная выполнением некоторого действия, не зависит от состояния, в котором это действие было выполнено.

Через TS  будем обозначать множество систем переходов вида TS=(B,E,S,A,,s0), удовлетворяющих следующему свойству: (s1,a,s2), (s3,a,s4)(s1\s2,s2\s1)=(s3\s4,s4\s3). Согласно предыдущей теореме, верно, что система переходов, соответствующая произвольной ЭСС, принадлежит классу TS. Далее, с системой переходов TS=(B,E,S,A,,s0)TS  будем связывать функцию preTS:AP(B) и функцию postTS:AP(B) такие, что верно (s,a,s')    (preTS(a)=s\s'postTS(a)=s'\s). Неформально говоря, условия из preTS(a) перестают выполняться, а условия из postTS(a) начинают выполняться. Далее будем опускать нижний индекс и писать просто pre и post. Пусть TSN=(B,E,CN,UN,N,cin) — система переходов, соответствующая ЭСС N=(B,E,F,cin). Ясно, что для TSN верно: uUN    (pre(u)=upost(u)=u).

Пусть TS=(B,E,S,A,,s0), sS и aA. Тогда действие  a может выполниться  в s (обозначается En(a,s)), если существует s'S такое, что (s,a,s').

Как оказалось, для систем переходов из класса  TS  существует необходимое условие для выполнения действия в некотором состоянии.

Теорема 11  Пусть  TS=(B,E,S,A,,s0)TS, sS  и  aA. Тогда, если  En(a,s), то  pre(a)s  и  post(a)s=.

Доказательство. Предположим, что действие a может быть выполнено в состоянии s. Тогда для некоторого s'S имеем (s,a,s'). По определению функций pre и post, верно s\s'=pre(a) и s'\s=post(a), что означает pre(a)s и post(a)s=.  □

В общем случае необходимое условие, сформулированное выше, не является достаточным, о чем свидетельствует пример, приведенный на рис. 2.10. Данная система переходов принадлежит классу TS, а также имеем следующее: pre(a1)={b1}, post(a1)={b3} и pre(a2)={b2}, post(a2)={b4}. Далее, в состоянии s={b1,b4} получаем pre(a1)s и post(a1)s=. Однако a1 не может выполниться в состоянии s. Совсем другая ситуация складывается для систем переходов, соответствующих ЭСС.

Теорема 12  Пусть  TSN=(B,E,CN,UNU,N,cin)система переходов, соответствующая ЭСС  N=(B,E,F,cin). Тогда 

cCNuUNU    En(u,s)pre(u)c  и  post(u)c=.

Доказательство. Необходимость следует из теоремы 11. Теперь предположим, что cCN и uUN такие, что pre(u)c и post(u)c=. Однако pre(u)=u и post(u)=u. Значит, c'=(cu)uCN. Более того, имеем (c,u,c')N. Поэтому u может произойти в состоянии c.  □