网的分析方法学习教案

1、会计学1网的分析方法网的分析方法第一页，共32页。t2t1t4p1p2p3t3M0 : (0,1,0)M2: (0,0,1)M1 : (1,0,0)t1t2t3t4第2页/共32页第二页，共32页。第3页/共32页第三页，共32页。定理定理(dngl)3.3(dngl)3.3、3.43.4和和3.53.5在无界在无界PetriPetri网中还成立吗？网中还成立吗？第4页/共32页第四页，共32页。第5页/共32页第五页，共32页。第6页/共32页第六页，共32页。p1p2t1t2p4t3t4p3M0 : (1,0,0,0)t1t2(0,1,1,0)t4(0,0,0,1)(1,0, ,0)(0,

2、1, ,0)t2t1(1,0, ,0)t4(0,0, ,1)t3(1,0, ,0)新新(1,0, 1,0)新新新新新旧旧新端点(dun din)第7页/共32页第七页，共32页。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第8页/共32页第八页，共32页。第9页/共32页第九页，共32页。aij=aij+-aij- , i 1,2,n,j 1,2,maij+=1, if ti,sj()F0, other i 1,2,n,j 1,2,maij-=1,

3、if sj,ti()F0, other i 1,2,n,j 1,2,m第10页/共32页第十页，共32页。ijn mAa+=ijn mAa-=, , iiiAAA+-, , jjjAAA+-M=M p1( ),M p2(),M pm()T第11页/共32页第十一页，共32页。p1p2t1t2p4t3t4p3p1p2t1t2p4t3t4p3A- =0 1 0 01 0 0 00 0 1 10 1 1 0p1p2t1t2p4t3t4p3A+ =1 0 0 00 1 1 01 0 0 00 0 0 1A=A+ -A- =p1p2t1t2p4t3t4p31 -1 0 0-1 1 1 01 0 -1 -

4、10 -1 -1 1第12页/共32页第十二页，共32页。 MTAi-n引理引理3.2. 设设PN=(P,T;F, M0)为一个为一个(y )Petri网。网。A为为PN的关联矩阵，的关联矩阵， 如果如果Mti M，则有，则有 n定理定理(dngl)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

5、 M0 0可达的一个必要条件，而非充分条件。可达的一个必要条件，而非充分条件。第13页/共32页第十三页，共32页。第14页/共32页第十四页，共32页。第15页/共32页第十五页，共32页。第16页/共32页第十六页，共32页。第17页/共32页第十七页，共32页。t2t1t4p1p2p3t3M0 : (0,1,0)M2: (0,0,1)M1 : (1,0,0)t1t2t3t4(t1t2+t3t4)* t1(t1t2+t3t4)* ( +t1+t3) 这里这里(zhl)Qt=M0 , M1 , M2第18页/共32页第十八页，共32页。终止符集终止符集标注标注无标注类无标注类无空标注类无空标

6、注类含空标注类含空标注类L-型型Lf LL G-型型GfGG T-型型TfTT P-型型PfPP 第19页/共32页第十九页，共32页。RLPNLCFLCSLu每种正规语言每种正规语言(yyn)(yyn)（RLRL）都是）都是PetriPetri网语言网语言(yyn)(yyn)（PNLPNL）u每种每种PetriPetri网语言网语言(yyn)(yyn)都是上下文有关语言都是上下文有关语言(yyn)(yyn)（CSLCSL）uPetriPetri网语言网语言(yyn)(yyn)类同上下文无关语言类同上下文无关语言(yyn)(yyn)类（类（CFLCFL）是两个相交但互不包含的语言）是两个相交但

7、互不包含的语言(yyn)(yyn)类类PNLPNL同同ChomskyChomsky体系体系(tx)(tx)中各型语言中各型语言的关系的关系第20页/共32页第二十页，共32页。第21页/共32页第二十一页，共32页。第22页/共32页第二十二页，共32页。第23页/共32页第二十三页，共32页。第24页/共32页第二十四页，共32页。1FF=1nnFFF-=1nnFF+=()0idnnFFFPT+= 称称F+为流关系为流关系(gun x)F的传递闭包。的传递闭包。id表示自反关系表示自反关系(gun x)。n定义定义3.9. 设设 N=(B,E;G)为一个网。如果为一个网。如果 （1） b B

8、：|b| 1 |b| 1 （2） x, y BE：(x,y) G+ (y, x) G+ 则称则称N为一个为一个出现网出现网，其中，其中G+表示流关系表示流关系G的传递闭包。的传递闭包。n出现网中没有情态（标识）的概念，它是通过流关系来描述系统中事件发生的轨迹。出现网中没有情态（标识）的概念，它是通过流关系来描述系统中事件发生的轨迹。第25页/共32页第二十五页，共32页。u事件事件e1e1和和e2e2存在并发关系当且仅当存在并发关系当且仅当N N中存在一个中存在一个(y )(y )切切u u，使得，使得e1e1u u且且e2e2u uu事件事件e1e1和和e2e2存在固定的顺序关系当且仅当存在固定的顺序关系当且仅当N N中存在一条线中存在一条线l l，使得，使得e1e1l l且且e2e2l l第26页/共32页第二十六页，共32页。第27页/共32页第二十七页，共32页。p1t1t2p4t5p3p2t3t4p5e4e1(p2)b1(t1)(p1)b2(p3)b3(t3)e2e3(p2)b4(t1)(p1)b5(p3)b6(t2)(t4)e5(p4)b7(