第三部分网的分析方法课件.ppt

1、第三部分 Petri网的分析方法提纲n可达标识图与可覆盖性树可达标识图与可覆盖性树n关联矩阵与状态方程关联矩阵与状态方程nPetri网语言网语言nPetri网进程网进程可达标识图与可覆盖性树n对于有界对于有界Petri网，其可达标识集网，其可达标识集R(M0)是一个有限集合，因此可以以是一个有限集合，因此可以以R(M0)作为顶点集，以标作为顶点集，以标识之间的直接可达关系为弧集构成一个有向图，称为识之间的直接可达关系为弧集构成一个有向图，称为Petri网的可达标识图（网的可达标识图（reachable marking graph）。）。n定义定义3.1.设设PN=(P,T;F,M0)为一个有界

2、为一个有界Petri网网。PN的的可达标识图可达标识图定义为一个三元组定义为一个三元组RG(PN)=(R(M0),E,L)，其中，其中 E=(Mi,Mj)|Mi,Mj R(M0),tk T:Mi tk Mj L:ET，L(Mi,Mj)=tk 当且仅当当且仅当Mi tk Mj 称称R(M0)为顶点集，为顶点集，E为弧（边）集，为弧（边）集，若若L(Mi,Mj)=tk，则称，则称tk为弧为弧(Mi,Mj)的旁标。的旁标。t2t1t4p1p2p3t3M0:(0,1,0)M2:(0,0,1)M1:(1,0,0)t1t2t3t4可达标识图与可覆盖性树n通过可达标识图通过可达标识图RG(PN)可以分析有界

3、可以分析有界Petri网网PN的各种性质。的各种性质。n定理定理3.1.对任意对任意Mi,Mj R(M0)，Mj是从是从 Mi可达的当且仅当在可达的当且仅当在RG(PN)中，从中，从Mi到到Mj存在一条有向路。存在一条有向路。n推论推论3.1.在在RG(PN)中，从中，从M0到每个结点都有一条有向路。到每个结点都有一条有向路。n推论推论3.2.M R(M0)是是PN的一个死标识当且仅当在的一个死标识当且仅当在RG(PN)中，中，M是一个终端标识。是一个终端标识。n定理定理3.2.设设pj P，在，在Petri网网PN中中pj的界的界 B(pj)等于等于RG(PN)中中各个顶点向量的第各个顶点向

4、量的第j个分量的最大值。个分量的最大值。n推论推论3.3.PN是安全的当且仅当是安全的当且仅当RG(PN)中中每个顶点的向量都是每个顶点的向量都是0-1向量。向量。可达标识图与可覆盖性树n定理定理3.3.有界有界Petri网网PN是活的当且仅当在是活的当且仅当在RG(PN)中，从顶点中，从顶点M0出发的每条有向路都走入一个强连通子图，而且在每个这样的强出发的每条有向路都走入一个强连通子图，而且在每个这样的强连通子图中，每个连通子图中，每个t T至少是一条有向弧的旁标。至少是一条有向弧的旁标。n定理定理3.4.有界有界Petri网网PN的两个变迁的两个变迁t1和和t2处于公平关系的充分必处于公平

5、关系的充分必要条件是在要条件是在RG(PN)的每条有向回路的每条有向回路C中，中，t1是其中的一条弧的旁是其中的一条弧的旁标当且仅当标当且仅当t2也是其中一条弧的旁标。也是其中一条弧的旁标。n定理定理3.5.PN是公平是公平Petri网的充分必要条件是在网的充分必要条件是在RG(PN)的每条有的每条有向回路向回路C中，每个中，每个 t T 都至少是都至少是C中一条弧中一条弧的旁标。的旁标。定理定理3.33.3、3.43.4和和3.53.5在无界在无界PetriPetri网中还成立吗？网中还成立吗？可达标识图与可覆盖性树n若若PN不是有界网，则不是有界网，则R(M0)是一个无限集合，无法画出是一

6、个无限集合，无法画出PN的可达标识图。的可达标识图。n为了用有限形式表达一个有无限个状态的系统的运行情况，引入一个表示无为了用有限形式表达一个有无限个状态的系统的运行情况，引入一个表示无界量的符号界量的符号。具有下述性质：具有下述性质：（1）对任意正整数）对任意正整数n：n，n=（2）n当库所当库所pj中的标识数在中的标识数在Petri网的运行过程中趋向于无限增长时，就把标识网的运行过程中趋向于无限增长时，就把标识向量中的第向量中的第j个分量改为个分量改为 ，以此覆盖所有这类标识。，以此覆盖所有这类标识。n通过引入通过引入 ，就可以用有限树来反映无界，就可以用有限树来反映无界Petri网的运行

7、情况，称该有限树网的运行情况，称该有限树为为Petri网网PN的的可覆盖性树可覆盖性树（coverability tree），记为），记为CT(PN)。可达标识图与可覆盖性树n算法算法3.1.Petri网可覆盖性树的构造算法网可覆盖性树的构造算法 输入：输入：PN=(P,T;F,M0)输出：输出：CT(PN)算法步骤：算法步骤：Step0：以：以M0作为作为CT(PN)的根结点，并标之以的根结点，并标之以“新新”；Step1：While 存在标注为存在标注为“新新”的结点的结点 Do 任选一个标注为任选一个标注为“新新”的结点，设为的结点，设为M；Step2：If 从从M0 到到M的有向路上有

8、一个结点的标识等于的有向路上有一个结点的标识等于M Then 把把M的标注改为的标注改为“旧旧”，返回，返回Step1；Step3：If t T:Mt Then 把把M的标注改为的标注改为“端点端点”，返回，返回Step1 Step4：For 每个满足每个满足Mt 的的t T Do 4.1：计算计算MtM中的中的M；4.2：If 从从M0 到到M的有向路上存在的有向路上存在M使使MM Then 找出使找出使M(pj)的充分必要条件是的充分必要条件是 MTAi-n引理引理3.2.设设PN=(P,T;F,M0)为一个为一个Petri网网。A为为PN的关联矩阵，的关联矩阵，如果如果Mti M，则，则

9、有有 n定理定理3.2.设设PN=(P,T;F,M0)为一个为一个Petri网网。A为为PN的关联矩阵，的关联矩阵，若若M R(M0)，则，则存在非负整数的存在非负整数的n维向量维向量X，使得，使得 M=M0+ATX M=M+Ai()T 上式称为上式称为Petri网的网的状态方程状态方程（state equation）。）。状态方程是状态方程是M M从从M M0 0可达的一个必要条件，而非充分条件。可达的一个必要条件，而非充分条件。关联矩阵与状态方程n证：证：变迁发生序列与Petri网语言nPetri网进行分析的另一种方法是考察网系统中所有可能网进行分析的另一种方法是考察网系统中所有可能发生的

10、变迁序列以及这些序列构成的集合的性质。发生的变迁序列以及这些序列构成的集合的性质。n一个字母表上满足某些特定条件的字符串的集合，称为该一个字母表上满足某些特定条件的字符串的集合，称为该字母表上的一个语言。字母表上的一个语言。n将将Petri网的变迁集网的变迁集T看作一个字母表，或者给出变迁集看作一个字母表，或者给出变迁集到某个字母表到某个字母表上的一个映射，那么该上的一个映射，那么该Petri网所有可能网所有可能发生的变迁序列（或其映射）的集合就是发生的变迁序列（或其映射）的集合就是T（或（或）上的）上的一个语言。一个语言。变迁发生序列与Petri网语言n定义定义3.4.设设PN=(P,T;F

11、,M0)为一个为一个Petri网。网。:T 为标注函数，为标注函数，Qt R(M0)。令。令 L=()*|T*:M0 M,M Qt L=()*|(T*:M0 M)(M Qt，M M)（1）若）若Qt是预先给定是预先给定R(M0)的一个子集，则称的一个子集，则称L为为PN产生的产生的L-型语言型语言；L称为称为PN产生的产生的G-型语言型语言。（2）若）若Qt=M R(M0)|t T:Mt，则称，则称L为为PN产生的产生的T-型语型语言言。（3）若）若Qt=R(M0)，则称，则称L为为PN产生的产生的P-型语言型语言。变迁发生序列与Petri网语言n定义定义3.5.设设PN=(P,T;F,M0)

12、为一个为一个Petri网。网。L是是PN产生的产生的L-型型（G-型，型，T-型，型，P-型）语言型）语言。对于。对于标注函数标注函数:T：（1）若）若=T，且，且t T:(t)=t，则称，则称L是是PN产生的产生的L-型（型（G-型，型，T-型，型，P-型）型）无标注语言无标注语言，记为，记为Lf（Gf，Tf，Pf）（2）若）若t T:(t)（表示空串），则称表示空串），则称L是是PN产生的产生的L-型型（G-型，型，T-型，型，P-型）型）无空标注语言无空标注语言，记为，记为L（G，T，P）；）；否则称否则称L是是PN产生的产生的L-型（型（G-型，型，T-型，型，P-型）型）含空标注语言

13、含空标注语言，记为记为L （G ，T ，P ）。）。变迁发生序列与Petri网语言n设设Qt=M1，则，则 Lf(PN)=nTf(PN)=nPf(PN)=t2t1t4p1p2p3t3M0:(0,1,0)M2:(0,0,1)M1:(1,0,0)t1t2t3t4(t1t2+t3t4)*t1(t1t2+t3t4)*(+t1+t3)这里这里Qt=M0,M1,M2变迁发生序列与Petri网语言终止符集终止符集标注标注无标注类无标注类无空标注类无空标注类含空标注类含空标注类L-型型Lf LL G-型型GfGG T-型型TfTT P-型型PfPP 变迁发生序列与Petri网语言RLPNLCFLCSLu每种正

14、规语言（每种正规语言（RLRL）都是）都是PetriPetri网语言（网语言（PNLPNL）u每种每种PetriPetri网语言都是上下文有关语言（网语言都是上下文有关语言（CSLCSL）uPetriPetri网语言类同上下文无关语言类（网语言类同上下文无关语言类（CFLCFL）是两个相交但互不包含的语言类）是两个相交但互不包含的语言类PNLPNL同同ChomskyChomsky体系中各型语言的关系体系中各型语言的关系变迁发生序列与Petri网语言n定义定义3.6.设设PN=(P,T;F,M0)为一个为一个Petri网。网。称称 L0(PN)=T*|M0 M 或或 L0(PN)=T*|M R(

15、M0):M0 M 为为PN所确定所确定的的P-型无标注语言型无标注语言。简称为。简称为PN所确定的语言。所确定的语言。nL0(PN)是是Petri网网PN从初始标识从初始标识M0出发的一切可发生的变迁序列出发的一切可发生的变迁序列的集合。的集合。n由于由于M0 R(M0)，所以总有，所以总有L0(PN)。变迁发生序列与Petri网语言n设设 为一个串，为一个串，L为一个语言，记为一个语言，记 Pref()=x|y:xy=Suff()=x|y:yx=Pref(L)=x|L:x Pref()Suff(L)=x|L:x Suff()n定义定义3.7.设设L为一种语言，如果为一种语言，如果 Pref(

16、L)=L 则称则称L为一种为一种前缀语言前缀语言。n定理定理3.3.Petri网网PN=(P,T;F,M0)所确定的语言所确定的语言L0(PN)是一种前缀语言，即是一种前缀语言，即 Pref(L0(PN)=L0(PN)变迁发生序列与Petri网语言n在形式语言理论中，在形式语言理论中，Pumping引理是正规语言和上下文无关语言的一个重引理是正规语言和上下文无关语言的一个重要性质。要性质。n定理定理3.4.设设PN=(P,T;F,M0)为一个有界为一个有界Petri网，网，L0(PN)。如果。如果|R(M0)|，则，则 可写成可写成=xyz的形式，其中的形式，其中x,y,z T*,|xy|R(

17、M0)|且且|y|1，使得对任意非负整数，使得对任意非负整数i，都有，都有xyiz L0(PN)。注：注：RG(PN)可看作是有限自动机的一个图形表示。可看作是有限自动机的一个图形表示。n推论推论3.1.设设PN=(P,T;F,M0)为一个有界为一个有界Petri网，网，若若 L0(PN)，使，使得得|R(M0)|，则，则L0(PN)是一个无限集。是一个无限集。提纲n可达标识图与可覆盖性树可达标识图与可覆盖性树n关联矩阵与状态方程关联矩阵与状态方程nPetri网语言网语言nPetri网进程网进程Petri网进程nPetri网语言不能很好地反映系统中的并发行为。为此网论中引入了网语言不能很好地反

18、映系统中的并发行为。为此网论中引入了Petri网进程的概念。网进程的概念。nPetri网进程的概念是建立在出现网（网进程的概念是建立在出现网（occurrence net）和网映射等概念基础上的。）和网映射等概念基础上的。n定义定义3.8.设设N=(P,T;F)为一个网，定义为一个网，定义1FF=1nnFFF-=1nnFF+=()0idnnFFFPT+=称称F+为流关系为流关系F的传递闭包。的传递闭包。id表示自反关系。表示自反关系。n定义定义3.9.设设 N=(B,E;G)为一个网。如果为一个网。如果 （1）b B：|b|1|b|1 （2）x,y BE：(x,y)G+(y,x)G+则称则称N

19、为一个为一个出现网出现网，其中，其中G+表示流关系表示流关系G的传递闭包。的传递闭包。n出现网中没有情态（标识）的概念，它是通过流关系来描述系统中事件发生的轨迹。出现网中没有情态（标识）的概念，它是通过流关系来描述系统中事件发生的轨迹。Petri网进程n定义定义3.10.设设N=(B,E;G)为一个出现网，为一个出现网，l B E。如果。如果 x,y l：(x,y)G+(y,x)G+则称则称l为为N的一个的一个线集线集。若。若l是是N的一个线集，且任意的一个线集，且任意ll都不是都不是N的线集，则称的线集，则称l为为N的的一条一条线线。n定义定义3.11.设设N=(B,E;G)为一个出现网，为

20、一个出现网，u B E。如果。如果 x,y u：(x,y)G+(y,x)G+则称则称u为为N的一个的一个切集切集。若。若u是是N的一个切集，且任意的一个切集，且任意uu都不是都不是N的切集，则称的切集，则称u为为N的一个的一个切切。n若若u是是N的一个切，且的一个切，且u B，则称，则称u为为N的一个的一个s-切。切。n设设u1,u2为为N的两个切，如果的两个切，如果 x u1，y u2：(x,y)G*，则记为，则记为u1 u2。u事件事件e e1 1和和e e2 2存在并发关系当且仅当存在并发关系当且仅当N N中存在一个切中存在一个切u u，使得，使得e1 u u且且e2 uu事件事件e1

21、1和和e2 2存在固定的顺序关系当且仅当存在固定的顺序关系当且仅当N中存在一条线中存在一条线l，使得，使得e1 1 l且且e2 2 lPetri网进程n定义定义3.12.设设N=(P,T;F)为一个网，为一个网，N=(B,E;G)为一个出现网。若映射为一个出现网。若映射：B E P T满足条件满足条件 （1）对于）对于(B)P,(E)T,x,y B E：(x,y)G (x),(y)F （2）e E：(e)=(e)，(e)=(e)则称则称 定义了定义了N到到N的一个的一个映射映射，记为，记为：N N。n定义定义3.13.设设PN=(N,M0)=(P,T;F,M0)为一个为一个Petri网，网，N

22、=(B,E;G)为一个出为一个出现网。如果现网。如果：N N 满足条件满足条件 （1）b1,b2 B，b1 b2：(b1)=(b2)b1 b2 b1 b2 （2）p P：|b|(b)=p b=|M0(p)则称则称(N,)为为PN的一个的一个进程进程（process）。Petri网进程p1t1t2p4t5p3p2t3t4p5e4e1(p2)b1(t1)(p1)b2(p3)b3(t3)e2e3(p2)b4(t1)(p1)b5(p3)b6(t2)(t4)e5(p4)b7(p5)b8(t5)e6(p2)b9Petri网进程n定义定义3.14.设设PN=(N,M0)=(P,T;F,M0)为一个为一个Pe

23、tri网，网，N=(B,E;G)为一个出为一个出现网。如果现网。如果：N N 满足条件满足条件 （1）b1,b2 B，b1 b2：(b1)=(b2)(b1 b2 b1=b2=)(b1 b2 b1=b2=)（2）p P：|b|(b)=p b=|=M0(p)则称则称(N,)为为PN的一个的一个满进程满进程（process）。n定理定理3.5.设设(N,)为为Petri网网PN=(N,M0)=(P,T;F,M0)的一个满进程，则对的的一个满进程，则对的任一个任一个s-切切u，都存在，都存在M R(M0)使得使得|b|b u (b)=p|=M(p)简记为简记为 (u)=M。Petri网进程n证证.令令

24、u0=b|b=，显然，显然u0是是N的一个的一个s-切，且切，且 (u0)=M0。设。设u为为N的任的任一个一个s-切。显然切。显然u0 u，记，记 E(u0,u)=e E|b0 u0,b u:(b0,e)G+(e,b)G+下面对下面对|E(u0,u)|用数学归纳法证明定理的结论。用数学归纳法证明定理的结论。当当|E(u0,u)|=0时，显然时，显然u=u0，从而，从而 (u0)=M0 R(M0)。设对设对|E(u0,u)|=k的任一个的任一个s-切切u，都有，都有M R(M0)使得使得 (u)=M。那么当那么当|E(u0,u)|=k+1时，易知存在时，易知存在N的一个的一个s-切切u1，使得

25、，使得 u0 u1 u（从而（从而 E(u0,u1)E(u0,u)），且），且|E(u0,u1)|=k。设设E(u0,u)-E(u0,u1)=e，则有，则有e u1，(u1-e)e=u (u1)=M1，(e)=t，因此有，因此有M1t。设。设M1tM，则，则 (u)=M。在简单有向图中，在简单有向图中，n若任何两个节点间是相互可达的，则称是强连通图；若任何两个节点间是相互可达的，则称是强连通图；n若任何两个节点之间至少从一个节点到另一个节点是可达的，则称是若任何两个节点之间至少从一个节点到另一个节点是可达的，则称是单向连通图或单侧连通图；单向连通图或单侧连通图；n若在图中略去边的方向，将它看成无向图后，图是连通的，则称该图若在图中略去边的方向，将它看成无向图后，图是连通的，则称该图是弱连通图。是弱连通图。n简单有向图中拥有附连通性质的最大子图就是强分图。简单有向图中拥有附连通性质的最大子图就是强分图。