第三部分网的分析方法

第三部分Petri网的分析方法提纲可达标识图与可覆盖性树关联矩阵与状态方程Petri网语言Petri网进程可达标识图与可覆盖性树对于有界Petri网，其可达标识集R(M0)是一个有限集合，因此可以以R(M0)作为顶点集，以标识之间的直接可达关系为弧集构成一个有向图，称为Petri网的可达标识图（reachablemarkinggraph）。定义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[tkMj}L:E→T，L(Mi,Mj)=tk当且仅当Mi[tkMj称R(M0)为顶点集，E为弧（边）集，若L(Mi,Mj)=tk，则称tk为弧(Mi,Mj)的旁标。t2t1t4p1p2p3t3M0:(0,1,0)M2:(0,0,1)M1:(1,0,0)t1t2t3t4可达标识图与可覆盖性树通过可达标识图RG(PN)可以分析有界Petri网PN的各种性质。定理3.1.对任意Mi,MjR(M0)，Mj是从Mi可达的当且仅当在RG(PN)中，从Mi到Mj存在一条有向路。推论3.1.在RG(PN)中，从M0到每个结点都有一条有向路。推论3.2.MR(M0)是PN的一个死标识当且仅当在RG(PN)中，M是一个终端标识。定理3.2.设pjP，在Petri网PN中pj的界B(pj)等于RG(PN)中各个顶点向量的第j个分量的最大值。推论3.3.PN是安全的当且仅当RG(PN)中每个顶点的向量都是0-1向量。可达标识图与可覆盖性树定理3.3.有界Petri网PN是活的当且仅当在RG(PN)中，从顶点M0出发的每条有向路都走入一个强连通子图，而且在每个这样的强连通子图中，每个tT至少是一条有向弧的旁标。定理3.4.有界Petri网PN的两个变迁t1和t2处于公平关系的充分必要条件是在RG(PN)的每条有向回路C中，t1是其中的一条弧的旁标当且仅当t2也是其中一条弧的旁标。定理3.5.PN是公平Petri网的充分必要条件是在RG(PN)的每条有向回路C中，每个tT都至少是C中一条弧的旁标。定理3.3、3.4和3.5在无界Petri网中还成立吗？？可达标识图与可覆盖性树若PN不是有界网，则R(M0)是一个无限集合，无法画出PN的可达标识图。为了用有限形式表达一个有无限个状态的系统的运行情况，引入一个表示无界量的符号。具有下述性质：（1）对任意正整数n：n，n=（2）当库所pj中的标识数在Petri网的运行过程中趋向于无限增长时，就把标识向量中的第j个分量改为，以此覆盖所有这类标识。通过引入，就可以用有限树来反映无界Petri网的运行情况，称该有限树为Petri网PN的可覆盖性树（coverabilitytree），记为CT(PN)。可达标识图与可覆盖性树算法3.1.Petri网可覆盖性树的构造算法输入：PN=(P,T;F,M0)输出：CT(PN)算法步骤：Step0：以M0作为CT(PN)的根结点，并标之以“新”；Step1：While存在标注为“新”的结点Do任选一个标注为“新”的结点，设为M；Step2：If从M0到M的有向路上有一个结点的标识等于MThen把M的标注改为“旧”，返回Step1；Step3：IftT:M[tThen把M的标注改为“端点”，返回Step1Step4：For每个满足M[t的tTDo4.1：计算M[tM’中的M’；4.2：If从M0到M的有向路上存在M’’使M’’M’Then找出使M’’(pj)M’(pj)的分量j，把M’的第j个分量改为；4.3：在CT(PN)中引入一个“新”结点M’，从M到M’画一条有向弧，并把此弧旁标以t；Step5：擦去结点M的“新”标注，返回Step1。可达标识图与可覆盖性树p1p2t1t2p4t3t4p3M0:(1,0,0,0)t1t2(0,1,1,0)t4(0,0,0,1)(1,0,,0)(0,1,,0)t2t1(1,0,,0)t4(0,0,,1)t3(1,0,,0)新新(1,0,1,0)新新新新新旧旧新端点可达标识图与可覆盖性树定理3.1.PN是有界Petri网当且仅当（按算法3.1构造的）CT(PN)中，每个结点的标识向量都不含有分量。对有界Petri网PN，按照算法3.1构造出来的树结构称为PN的可达性树（reachabilitytree），记为RT(PN)。定义3.2.设CT(PN)为Petri网的可覆盖性树。若将CT(PN)中标识向量相同的结点合并在一起，便得到PN的可覆盖性图，记为CG(PN)。M0:(1,0,0,0)t1t2(0,1,1,0)t4(0,0,0,1)(1,0,,0)(0,1,,0)t2(1,0,,0)t1t4(0,0,,1)(1,0,,0)t3t1t3提纲可达标识图与可覆盖性树关联矩阵与状态方程Petri网语言Petri网进程关联矩阵与状态方程网的结构可以用一个矩阵来表示，从而可以引入线性代数的方法对Petri网进行分析。定义3.3.设PN=(P,T;F,M0)为一个Petri网。P={p1,p2,,pm}，T={t1,t2,,tn}，则网N=(P,T;F)可以用一个n行m列矩阵A=[aij]nm（3.1）来表示，称A为PN（N）的关联矩阵（incidencematrix）。其中aij=aij+-aij-,iÎ1,2,,n{},jÎ1,2,,m{}aij+=1,ifti,sj()ÎF0,otherìíïîïiÎ1,2,,n{},jÎ1,2,,m{}aij-=1,ifsj,ti()ÎF0,otherìíïîïiÎ1,2,,n{},jÎ1,2,,m{}关联矩阵与状态方程PN的输出矩阵PN的输入矩阵行向量列向量标识MijnmAaijnmAa,,iiiAAA,,jjjAAAM=Mp1(),Mp2(),,Mpm()éëùûT关联矩阵与状态方程p1p2t1t2p4t3t4p3p1p2t1t2p4t3t4p3A-=0100100000110110p1p2t1t2p4t3t4p3A+=1000011010000001A=A+-A-=p1p2t1t2p4t3t4p31-100-111010-1-10-1-11关联矩阵与状态方程引理3.1.设PN=(P,T;F,M0)为一个Petri网。A为PN的关联矩阵，tiT，则M[ti的充分必要条件是MT³Ai*-引理3.2.设PN=(P,T;F,M0)为一个Petri网。A为PN的关联矩阵，如果M[tiM’，则有定理3.2.设PN=(P,T;F,M0)为一个Petri网。A为PN的关联矩阵，若MR(M0)，则存在非负整数的n维向量X，使得M=M0+ATX¢M=M+Ai*()T上式称为Petri网的状态方程（stateequation）。状态方程是M从M0可达的一个必要条件，而非充分条件。关联矩阵与状态方程证：变迁发生序列与Petri网语言Petri网进行分析的另一种方法是考察网系统中所有可能发生的变迁序列以及这些序列构成的集合的性质。一个字母表上满足某些特定条件的字符串的集合，称为该字母表上的一个语言。将Petri网的变迁集T看作一个字母表，或者给出变迁集到某个字母表上的一个映射，那么该Petri网所有可能发生的变迁序列（或其映射）的集合就是T（或）上的一个语言。变迁发生序列与Petri网语言定义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:M[t}，则称L为PN产生的T-型语言。（3）若Qt=R(M0)，则称L为PN产生的P-型语言。变迁发生序列与Petri网语言定义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网语言设Qt={M1}，则Lf(PN)=Tf(PN)=Pf(PN)=t2t1t4p1p2p3t3M0:(0,1,0)M2:(0,0,1)M1:(1,0,0)t1t2t3t4(t1•t2+t3•t4)*•t1(t1•t2+t3•t4)*•(+t1+t3)这里Qt={M0,M1,M2}变迁发生序列与Petri网语言终止符集标注无标注类无空标注类含空标注类L-型LfLLG-型GfGGT-型TfTTP-型PfPP变迁发生序列与Petri网语言RLPNLCFLCSL每种正规语言（RL）都是Petri网语言（PNL）每种Petri网语言都是上下文有关语言（CSL）Petri网语言类同上下文无关语言类（CFL）是两个相交但互不包含的语言类PNL同Chomsky体系中各型语言的关系变迁发生序列与Petri网语言定义3.6.设PN=(P,T;F,M0)为一个Petri网。称L0(PN)={T*|M0[M}或L0(PN)={T*|MR(M0):M0[M}为PN所确定的P-型无标注语言。简称为PN所确定的语言。L0(PN)是Petri网PN从初始标识M0出发的一切可发生的变迁序列的集合。由于M0R(M0)，所以总有L0(PN)。变迁发生序列与Petri网语言设为一个串，L为一个语言，记Pref()={x|y:xy=}Suff()={x|y:yx=}Pref(L)={x|L:xPref()}Suff(L)={x|L:xSuff()}定义3.7.设L为一种语言，如果Pref(L)=L则称L为一种前缀语言。定理3.3.Petri网PN=(P,T;F,M0)所确定的语言L0(PN)是一种前缀语言，即Pref(L0(PN))=L0(PN)变迁发生序列与Petri网语言在形式语言理论中，Pumping引理是正规语言和上下文无关语言的一个重要性质。定理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)可看作是有限自动机的一个图形表示。推论3.1.设PN=(P,T;F,M0)为一个有界Petri网，若L0(PN)，使得|||R(M0)|，则L0(PN)是一个无限集。提纲可达标识图与可覆盖性树关联矩阵与状态方程Petri网语言Petri网进程Petri网进程Petri网语言不能很好地反映系统中的并发行为。为此网论中引入了Petri网进程的概念。Petri网进程的概念是建立在出现网（occurrencenet）和网映射等概念基础上的。定义3.8.设N=(P,T;F)为一个网，定义1FF1nnFFF1nnFF0idnnFFFPT称F+为流关系F的传递闭包。id表示自反关系。定义3.9.设N=(B,E;G)