第三部分网的分析方法

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

2、(Mi,Mj)= tk 当且仅当Mi tk Mj 称R(M0)为顶点集，E为弧（边）集， 若L(Mi,Mj) = tk，则称tk为弧(Mi,Mj)的旁标。,可达标识图与可覆盖性树,通过可达标识图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 )等于R

3、G(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中，每个

4、 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的可覆盖性树（coverability tree），

5、记为CT(PN)。,可达标识图与可覆盖性树,算法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 tT:Mt Then 把M的标注改为“端点”，返回Step1 Step4： For 每个满足Mt 的tT Do 4.1： 计算MtM中的M； 4.2

6、： If 从M0 到M的有向路上存在M使MM Then 找出使M(pj) M(pj)的分量j，把M的第j个分量改为； 4.3： 在CT(PN)中引入一个“新”结点M，从M到M画一条有向弧，并把此弧旁标以t； Step5： 擦去结点M的“新”标注，返回Step1。,可达标识图与可覆盖性树,M0 : (1,0,0,0),t1,(1,0, ,0),新,新,(1,0, 1,0),新,新,新,新,新,旧,旧,新,端点,可达标识图与可覆盖性树,定理3.1. PN是有界Petri网当且仅当（按算法3.1构造的）CT(PN)中，每个结点的标识向量都不含有分量。 对有界Petri网PN，按照算法3.1构造出来的

7、树结构称为PN的可达性树（reachability tree），记为RT(PN)。 定义3.2. 设CT(PN)为Petri网的可覆盖性树。若将CT(PN)中标识向量相同的结点合并在一起，便得到PN的可覆盖性图，记为CG(PN)。,M0 : (1,0,0,0),t1,(1,0, ,0),(1,0, ,0),(1,0, ,0),提纲,可达标识图与可覆盖性树 关联矩阵与状态方程 Petri网语言 Petri网进程,关联矩阵与状态方程,网的结构可以用一个矩阵来表示，从而可以引入线性代数的方法对Petri网进行分析。 定义3.3. 设PN=(P,T;F, M0)为一个Petri网。 P=p1, p2,

8、pm ，T=t1, t2,tn ，则网N =(P,T;F)可以用一个n行m列矩阵 A=aijnm （3.1） 来表示，称A为PN（N）的关联矩阵（incidence matrix）。其中,关联矩阵与状态方程,PN的输出矩阵 PN的输入矩阵 行向量 列向量 标识M,关联矩阵与状态方程,p1,p2,t1,t2,p4,t3,t4,p3,0 1 0 0,1 0 0 0,0 0 1 1,0 1 1 0,1 0 0 0,0 1 1 0,1 0 0 0,0 0 0 1,1 -1 0 0,-1 1 1 0,1 0 -1 -1,0 -1 -1 1,关联矩阵与状态方程,引理3.1. 设PN=(P,T;F, M0)

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

10、一个字母表上满足某些特定条件的字符串的集合，称为该字母表上的一个语言。 将Petri网的变迁集T看作一个字母表，或者给出变迁集到某个字母表上的一个映射，那么该Petri网所有可能发生的变迁序列（或其映射）的集合就是T（或）上的一个语言。,变迁发生序列与Petri网语言,定义3.4.设PN=(P,T;F, M0)为一个Petri网。 : T为标注函数，Qt R(M0)。令 L=() *|T*:M0M,M Qt L=() *|(T*:M0M) (MQt ，MM) （1）若Qt是预先给定R(M0)的一个子集，则称L为PN产生的L-型语言；L称为PN产生的G-型语言。 （2）若Qt =M R(M0)

11、|tT: Mt，则称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，且tT: (t)=t，则称L是PN产生的L-型（ G-型， T-型， P-型）无标注语言，记为Lf（ Gf， Tf， Pf） （2）若tT: (t)（表示空串），则称L是PN产生的L-型（ G-型， T-型， P-型）无空标注语言，记为L（ G， T， P）；否则称L是PN产生的L-型（ G-型，

12、T-型， P-型）含空标注语言，记为L （ G ， T ， P ）。,变迁发生序列与Petri网语言,设Qt=M1，则 Lf (PN)= Tf (PN)= Pf(PN)=,(t1t2+t3t4)* t1,(t1t2+t3t4)* (+t1+t3) 这里Qt=M0 , M1 , M2,变迁发生序列与Petri网语言,变迁发生序列与Petri网语言,RL,PNL,CFL,CSL,每种正规语言（RL）都是Petri网语言（PNL） 每种Petri网语言都是上下文有关语言（CSL） Petri网语言类同上下文无关语言类（CFL）是两个相交但互不包含的语言类,PNL同Chomsky体系中各型语言的关系,

13、变迁发生序列与Petri网语言,定义3.6.设PN=(P,T;F, M0)为一个Petri网。称 L0(PN)=T*| M0M 或 L0(PN)= T*| MR(M0): M0M 为PN所确定的P-型无标注语言。简称为PN所确定的语言。 L0(PN)是Petri网PN从初始标识M0出发的一切可发生的变迁序列的集合。 由于M0R(M0)，所以总有L0(PN)。,变迁发生序列与Petri网语言,设为一个串，L为一个语言，记 Pref()=x| y: xy= Suff()=x| y: yx= Pref(L)=x| L: xPref() Suff(L)=x| L: xSuff() 定义3.7.设L为一

14、种语言，如果 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,zT*,|xy| |R(M0)|且|y|1，使得对任意非负整数i，都有xyiz L0(PN)。 注：RG(PN)可看作是有限自动机的一个图形表示。 推论3.

15、1.设PN=(P,T;F, M0)为一个有界Petri网， 若 L0(PN)，使得|R(M0)|，则L0(PN) 是一个无限集。,提纲,可达标识图与可覆盖性树 关联矩阵与状态方程 Petri网语言 Petri网进程,Petri网进程,Petri网语言不能很好地反映系统中的并发行为。为此网论中引入了Petri网进程的概念。 Petri网进程的概念是建立在出现网（occurrence net）和网映射等概念基础上的。 定义3.8.设N=(P,T;F)为一个网，定义,称F+为流关系F的传递闭包。id表示自反关系。,定义3.9. 设N=(B,E;G)为一个网。如果 （1） bB：|b| 1 |b| 1

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

17、，则称u为N的一个切。 若u是N的一个切，且u B ，则称u为N的一个s-切。 设u1, u2为N的两个切，如果x u1，yu2 ： (x,y) G* ，则记为u1 u2。,事件e1和e2存在并发关系当且仅当N中存在一个切u，使得e1u且e2u 事件e1和e2存在固定的顺序关系当且仅当N中存在一条线l，使得e1l且e2l,Petri网进程,定义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)=

18、 (e) 则称定义了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网进程,Petri网进程,定义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）。 定理3.5. 设(N, )为Petri网PN=(N, M0 )=(