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

第三部分 Petri网的分析方法提纲n可达可达标识图标识图与可覆盖性与可覆盖性树树n关关联联矩矩阵阵与状与状态态方程方程nPetri网网语语言言nPetri网网进进程程可达标识图与可覆盖性树n对对于有界于有界Petri网，其可达网，其可达标识标识集集R(M0)是一个有限集合，因此可以以是一个有限集合，因此可以以R(M0)作作为顶为顶点集，以点集，以标识标识之之间间的直接可达关系的直接可达关系为为弧集构成一个有向弧集构成一个有向图图，称，称为为Petri网的可达网的可达标识图标识图（reachable marking graph）。）。n定定义义3.1.设设PN=(P,T;F,M0)为为一个有界一个有界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)可以分析有界可以分析有界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)中中各个各个顶点向量的第点向量的第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处处于公平关系的充分必于公平关系的充分必要条件是在要条件是在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)是一个无限集合，无法画出是一个无限集合，无法画出PN的可达的可达标识图标识图。n为为了用有限形式表达一个有无限个状了用有限形式表达一个有无限个状态态的系的系统统的运行情况，引入一个表示无的运行情况，引入一个表示无界量的符号界量的符号。具有下述性具有下述性质质：（1）对对任意正整数任意正整数n：n，n=（2）n当当库库所所pj中的中的标识标识数在数在Petri网的运行网的运行过过程中程中趋趋向于无限增向于无限增长时长时，就把，就把标识标识向向量中的第量中的第j个分量改个分量改为为 ，以此覆盖所有，以此覆盖所有这类标识这类标识。n通通过过引入引入 ，就可以用有限，就可以用有限树树来反映无界来反映无界Petri网的运行情况，称网的运行情况，称该该有限有限树为树为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的有向路上有一个的有向路上有一个结结点的点的标识标识等于等于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)的充分必要条件是的充分必要条件是 n引理引理3.2.设设PN=(P,T;F,M0)为一个为一个Petri网网。A为为PN的关联矩阵，的关联矩阵，如果如果Mti M，则，则有有 n定理定理3.2.设设PN=(P,T;F,M0)为一个为一个Petri网网。A为为PN的关联矩阵，的关联矩阵，若若M R(M0)，则，则存在非负整数的存在非负整数的n维向量维向量X，使得，使得 上式称为上式称为Petri网的网的状态方程状态方程（state equation）。）。状态方程是状态方程是M M从从M M0 0可达的一个必要条件，而非充分条件。可达的一个必要条件，而非充分条件。关联矩阵与状态方程n证证：变迁发生序列与Petri网语言nPetri网网进进行分析的另一种方法是考察网系行分析的另一种方法是考察网系统统中所有可能中所有可能发发生的生的变变迁序列以及迁序列以及这这些序列构成的集合的性些序列构成的集合的性质质。n一个字母表上一个字母表上满满足某些特定条件的字符串的集合，称足某些特定条件的字符串的集合，称为该为该字母表上的一个字母表上的一个语语言。言。n将将Petri网的网的变变迁集迁集T看作一个字母表，或者看作一个字母表，或者给给出出变变迁集迁集到某个字母表到某个字母表上的一个映射，那么上的一个映射，那么该该Petri网所有可能网所有可能发发生的生的变变迁序列（或其映射）的集合就是迁序列（或其映射）的集合就是T（或（或）上的）上的一个一个语语言。言。变迁发生序列与Petri网语言n定定义义3.4.设设PN=(P,T;F,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)为为一个一个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-型）型）含空含空标标注注语语言言，记为记为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每种正规语言（每种正规语言（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(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(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(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网网语言不能很好地反映系言不能很好地反映系统中的并中的并发行行为。为此网此网论中引入了中引入了Petri网网进程的概念。程的概念。nPetri网网进程的概念是建立在出程的概念是建立在出现网（网（occurrence net）和网映射等概念基）和网映射等概念基础上的。上的。n定定义义3.8.设设N=(P,T;F)为为一个网，定一个网，定义义 称称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为一个为一个出现网出现网，其中，其中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)为为一个出一个出现现网，网，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 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=(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)为为一个一个Petri网，网，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证证.令令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，使得，使得 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简单简单有向有向图图中中拥拥有附有附连连通性通性质质的最大子的最大子图图就是就是强强分分图图。