第三部分Petri網(wǎng)的分析方法第三部分Petri網(wǎng)的分析方法提綱可達標識圖與可覆蓋性樹關(guān)聯(lián)矩陣與狀態(tài)方程Petri網(wǎng)語言Petri網(wǎng)進程提綱可達標識圖與可覆蓋性樹可達標識圖與可覆蓋性樹對于有界Petri網(wǎng)，其可達標識集R(M0)是一個有限集合，因此可以以R(M0)作為頂點集，以標識之間的直接可達關(guān)系為弧集構(gòu)成一個有向圖，稱為Petri網(wǎng)的可達標識圖（reachablemarkinggraph）。定義3.1.設PN=(P,T;F,M0)為一個有界Petri網(wǎng)。PN的可達標識圖定義為一個三元組RG(PN)=(R(M0),E,L)，其中

E={(Mi,Mj)|Mi,MjR(M0),tkT:Mi[tk>Mj}L:E→T，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可達標識圖與可覆蓋性樹對于有界Petri網(wǎng)，其可達標識集R(可達標識圖與可覆蓋性樹通過可達標識圖RG(PN)可以分析有界Petri網(wǎng)PN的各種性質(zhì)。定理3.1.

對任意Mi,MjR(M0)，Mj是從Mi可達的當且僅當在RG(PN)中，從Mi到Mj存在一條有向路。推論3.1.

在RG(PN)中，從M0到每個結(jié)點都有一條有向路。推論3.2.

MR(M0)是PN的一個死標識當且僅當在RG(PN)中，M是一個終端標識。定理3.2.

設pjP，在Petri網(wǎng)PN中pj的界B(pj)等于RG(PN)中各個頂點向量的第j個分量的最大值。推論3.3.PN是安全的當且僅當RG(PN)中每個頂點的向量都是0-1向量?？蛇_標識圖與可覆蓋性樹通過可達標識圖RG(PN)可以分析有界可達標識圖與可覆蓋性樹定理3.3.

有界Petri網(wǎng)PN是活的當且僅當在RG(PN)中，從頂點M0出發(fā)的每條有向路都走入一個強連通子圖，而且在每個這樣的強連通子圖中，每個tT至少是一條有向弧的旁標。定理3.4.

有界Petri網(wǎng)PN的兩個變遷t1和t2處于公平關(guān)系的充分必要條件是在RG(PN)的每條有向回路C中，t1是其中的一條弧的旁標當且僅當t2也是其中一條弧的旁標。定理3.5.PN是公平Petri網(wǎng)的充分必要條件是在RG(PN)的每條有向回路C中，每個tT都至少是C中一條弧的旁標。定理3.3、3.4和3.5在無界Petri網(wǎng)中還成立嗎？？可達標識圖與可覆蓋性樹定理3.3.有界Petri網(wǎng)PN是活可達標識圖與可覆蓋性樹若PN不是有界網(wǎng)，則R(M0)是一個無限集合，無法畫出PN的可達標識圖。為了用有限形式表達一個有無限個狀態(tài)的系統(tǒng)的運行情況，引入一個表示無界量的符號。具有下述性質(zhì)：（1）對任意正整數(shù)n：>n，n=

（2）當庫所pj中的標識數(shù)在Petri網(wǎng)的運行過程中趨向于無限增長時，就把標識向量中的第j個分量改為，以此覆蓋所有這類標識。通過引入，就可以用有限樹來反映無界Petri網(wǎng)的運行情況，稱該有限樹為Petri網(wǎng)PN的可覆蓋性樹（coverabilitytree），記為CT(PN)?？蛇_標識圖與可覆蓋性樹若PN不是有界網(wǎng)，則R(M0)是一個無可達標識圖與可覆蓋性樹算法3.1.Petri網(wǎng)可覆蓋性樹的構(gòu)造算法輸入：PN=(P,T;F,M0)

輸出：CT(PN)

算法步驟：

Step0：以M0作為CT(PN)的根結(jié)點，并標之以“新”；

Step1：While存在標注為“新”的結(jié)點Do

任選一個標注為“新”的結(jié)點，設為M；

Step2：If從M0到M的有向路上有一個結(jié)點的標識等于MThen

把M的標注改為“舊”，返回Step1；

Step3：IftT:M[t>Then

把M的標注改為“端點”，返回Step1Step4：For每個滿足M[t>的tTDo4.1：計算M[t>M’中的M’；

4.2：If從M0到M的有向路上存在M’’使M’’<M’Then

找出使M’’(pj)<M’(pj)的分量j，把M’的第j個分量改為；

4.3：在CT(PN)中引入一個“新”結(jié)點M’，從M到M’畫一條有向弧，并把此弧旁標以t；

Step5：擦去結(jié)點M的“新”標注，返回Step1?？蛇_標識圖與可覆蓋性樹算法3.1.Petri網(wǎng)可覆蓋性樹的可達標識圖與可覆蓋性樹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)新新新新新舊舊新端點可達標識圖與可覆蓋性樹p1p2t1t2p4t3t4p3M0可達標識圖與可覆蓋性樹定理3.1.PN是有界Petri網(wǎng)當且僅當（按算法3.1構(gòu)造的）CT(PN)中，每個結(jié)點的標識向量都不含有分量。對有界Petri網(wǎng)PN，按照算法3.1構(gòu)造出來的樹結(jié)構(gòu)稱為PN的可達性樹（reachabilitytree），記為RT(PN)。定義3.2.設CT(PN)為Petri網(wǎng)的可覆蓋性樹。若將CT(PN)中標識向量相同的結(jié)點合并在一起，便得到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可達標識圖與可覆蓋性樹定理3.1.PN是有界Petri網(wǎng)當提綱可達標識圖與可覆蓋性樹關(guān)聯(lián)矩陣與狀態(tài)方程Petri網(wǎng)語言Petri網(wǎng)進程提綱可達標識圖與可覆蓋性樹關(guān)聯(lián)矩陣與狀態(tài)方程網(wǎng)的結(jié)構(gòu)可以用一個矩陣來表示，從而可以引入線性代數(shù)的方法對Petri網(wǎng)進行分析。定義3.3.設PN=(P,T;F,M0)為一個Petri網(wǎng)。P={p1,p2,,pm}

，T={t1,t2,,tn}，則網(wǎng)N=(P,T;F)可以用一個n行m列矩陣

A=[aij]nm

（3.1）來表示，稱A為PN（N）的關(guān)聯(lián)矩陣（incidencematrix）。其中關(guān)聯(lián)矩陣與狀態(tài)方程網(wǎng)的結(jié)構(gòu)可以用一個矩陣來表示，從而可以引入關(guān)聯(lián)矩陣與狀態(tài)方程PN的輸出矩陣PN的輸入矩陣行向量列向量標識M關(guān)聯(lián)矩陣與狀態(tài)方程PN的輸出矩陣關(guān)聯(lián)矩陣與狀態(tài)方程p1p2t1t2p4t3t4p3p1p2t1t2p4t3t4p3A-=0100100000110110p1p2t1t2p4t3t4p3A+=1000011010000001A=A+-A-

=p1p2t1t2p4t3t4p31-100-111010-1-10-1-11關(guān)聯(lián)矩陣與狀態(tài)方程p1p2t1t2p4t3t4p3p1p2t關(guān)聯(lián)矩陣與狀態(tài)方程引理3.1.設PN=(P,T;F,M0)為一個Petri網(wǎng)。A為PN的關(guān)聯(lián)矩陣，tiT，則M[ti>的充分必要條件是引理3.2.設PN=(P,T;F,M0)為一個Petri網(wǎng)。A為PN的關(guān)聯(lián)矩陣，如果M[ti>M’，則有定理3.2.設PN=(P,T;F,M0)為一個Petri網(wǎng)。A為PN的關(guān)聯(lián)矩陣，若MR(M0)，則存在非負整數(shù)的n維向量X，使得

上式稱為Petri網(wǎng)的狀態(tài)方程（stateequation）。狀態(tài)方程是M從M0可達的一個必要條件，而非充分條件。關(guān)聯(lián)矩陣與狀態(tài)方程引理3.1.設PN=(P,T;F,M0關(guān)聯(lián)矩陣與狀態(tài)方程證：關(guān)聯(lián)矩陣與狀態(tài)方程證：變遷發(fā)生序列與Petri網(wǎng)語言Petri網(wǎng)進行分析的另一種方法是考察網(wǎng)系統(tǒng)中所有可能發(fā)生的變遷序列以及這些序列構(gòu)成的集合的性質(zhì)。一個字母表上滿足某些特定條件的字符串的集合，稱為該字母表上的一個語言。將Petri網(wǎng)的變遷集T看作一個字母表，或者給出變遷集到某個字母表上的一個映射，那么該Petri網(wǎng)所有可能發(fā)生的變遷序列（或其映射）的集合就是T（或）上的一個語言。變遷發(fā)生序列與Petri網(wǎng)語言Petri網(wǎng)進行分析的另一種方變遷發(fā)生序列與Petri網(wǎng)語言定義3.4.設PN=(P,T;F,M0)為一個Petri網(wǎng)。:T→為標注函數(shù)，QtR(M0)。令

L={()*|T*:M0[>M,MQt}L’={()*|(T*:M0[>M)(M’Qt，MM’)}

（1）若Qt是預先給定R(M0)的一個子集，則稱L為PN產(chǎn)生的L-型語言；L’稱為PN產(chǎn)生的G-型語言。（2）若Qt={MR(M0)|tT:M[t>}，則稱L為PN產(chǎn)生的T-型語言。（3）若Qt=

R(M0)

，則稱L為PN產(chǎn)生的P-型語言。變遷發(fā)生序列與Petri網(wǎng)語言定義3.4.設PN=(P,T;變遷發(fā)生序列與Petri網(wǎng)語言定義3.5.設PN=(P,T;F,M0)為一個Petri網(wǎng)。L是PN產(chǎn)生的L-型（G-型，T-型，P-型）語言。對于標注函數(shù):T→：（1）若=T，且tT:(t)=t，則稱L是PN產(chǎn)生的L-型（G-型，T-型，P-型）無標注語言，記為Lf（Gf，Tf，Pf）（2）若tT:(t)（表示空串），則稱L是PN產(chǎn)生的L-型（G-型，T-型，P-型）無空標注語言，記為L（G，T，P）；否則稱L是PN產(chǎn)生的L-型（G-型，T-型，P-型）含空標注語言，記為L（G

，T

，P

）。變遷發(fā)生序列與Petri網(wǎng)語言定義3.5.設PN=(P,T;變遷發(fā)生序列與Petri網(wǎng)語言設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}變遷發(fā)生序列與Petri網(wǎng)語言設Qt={M1}，則Lf(變遷發(fā)生序列與Petri網(wǎng)語言終止符集標注無標注類無空標注類含空標注類L-型Lf

LLG-型GfGGT-型TfTTP-型PfPP變遷發(fā)生序列與Petri網(wǎng)語言終止符集標注無標注類無空標注類變遷發(fā)生序列與Petri網(wǎng)語言RLPNLCFLCSL每種正規(guī)語言（RL）都是Petri網(wǎng)語言（PNL）每種Petri網(wǎng)語言都是上下文有關(guān)語言（CSL）Petri網(wǎng)語言類同上下文無關(guān)語言類（CFL）是兩個相交但互不包含的語言類PNL同Chomsky體系中各型語言的關(guān)系變遷發(fā)生序列與Petri網(wǎng)語言RLPNLCFLCSL每種正規(guī)變遷發(fā)生序列與Petri網(wǎng)語言定義3.6.設PN=(P,T;F,M0)為一個Petri網(wǎng)。稱

L0(PN)={T*|M0[>M}

或L0(PN)={T*|MR(M0):M0[>M}

為PN所確定的P-型無標注語言。簡稱為PN所確定的語言。L0(PN)是Petri網(wǎng)PN從初始標識M0出發(fā)的一切可發(fā)生的變遷序列的集合。由于M0R(M0)，所以總有L0(PN)。變遷發(fā)生序列與Petri網(wǎng)語言定義3.6.設PN=(P,T;變遷發(fā)生序列與Petri網(wǎng)語言設為一個串，L為一個語言，記

Pref()={x|y:xy=}Suff()={x|y:yx=}Pref(L)={x|L:xPref()}Suff(L)={x|L:xSuff()}定義3.7.設L為一種語言，如果

Pref(L)=L

則稱L為一種前綴語言。定理3.3.Petri網(wǎng)PN=(P,T;F,M0)所確定的語言L0(PN)是一種前綴語言，即

Pref(L0(PN))=L0(PN)變遷發(fā)生序列與Petri網(wǎng)語言設為一個串，L為一個語言，記變遷發(fā)生序列與Petri網(wǎng)語言在形式語言理論中，Pumping引理是正規(guī)語言和上下文無關(guān)語言的一個重要性質(zhì)。定理3.4.設PN=(P,T;F,M0)為一個有界Petri網(wǎng)，L0(PN)。如果|||R(M0)|，則可寫成=xyz的形式，其中x,y,zT*,|xy||R(M0)|且|y|1，使得對任意非負整數(shù)i，都有xyizL0(PN)。注：RG(PN)可看作是有限自動機的一個圖形表示。推論3.1.設PN=(P,T;F,M0)為一個有界Petri網(wǎng)，若L0(PN)，使得|||R(M0)|，則L0(PN)是一個無限集。變遷發(fā)生序列與Petri網(wǎng)語言在形式語言理論中，Pumpin提綱可達標識圖與可覆蓋性樹關(guān)聯(lián)矩陣與狀態(tài)方程Petri網(wǎng)語言Petri網(wǎng)進程提綱可達標識圖與可覆蓋性樹Petri網(wǎng)進程Petri網(wǎng)語言不能很好地反映系統(tǒng)中的并發(fā)行為。為此網(wǎng)論中引入了Petri網(wǎng)進程的概念。Petri網(wǎng)進程的概念是建立在出現(xiàn)網(wǎng)（occurrencenet）和網(wǎng)映射等概念基礎上的。定義3.8.設N=(P,T;F)為一個網(wǎng)，定義

稱F+為流關(guān)系F的傳遞閉包。id表示自反關(guān)系。定義3.9.設N=(B,E;G)為一個網(wǎng)。如果（1）bB：|?b|1|b?|1

（2）

x,yBE：(x,y)G+→(y,x)G+

則稱N為一個出現(xiàn)網(wǎng)，其中G+表示流關(guān)系G的傳遞閉包。出現(xiàn)網(wǎng)中沒有情態(tài)（標識）的概念，它是通過流關(guān)系來描述系統(tǒng)中事件發(fā)生的軌跡。Petri網(wǎng)進程Petri網(wǎng)語言不能很好地反映系統(tǒng)中的并發(fā)行Petri網(wǎng)進程定義3.10.設N=(B,E;G)為一個出現(xiàn)網(wǎng)，lBE。如果

x,yl：(x,y)G+(y,x)G+

則稱l為N的一個線集。若l是N的一個線集，且任意l’l都不是N的線集，則稱l為N的一條線。定義3.11.設N=(B,E;G)為一個出現(xiàn)網(wǎng)，uBE。如果

x,yu：(x,y)G+

(y,x)G+

則稱u為N的一個切集。若u是N的一個切集，且任意u’u都不是N的切集，則稱u為N的一個切。若u是N的一個切，且uB，則稱u為N的一個s-切。設u1,u2為N的兩個切，如果xu1，yu2

：(x,y)G*

，則記為u1

u2。事件e1和e2存在并發(fā)關(guān)系當且僅當N中存在一個切u，使得e1u且e2u事件e1和e2存在固定的順序關(guān)系當且僅當N中存在一條線l，使得e1l且e2lPetri網(wǎng)進程定義3.10.設N=(B,E;G)為一個出現(xiàn)Petri網(wǎng)進程定義3.12.設N=(P,T;F)為一個網(wǎng)，N=(B,E;G)為一個出現(xiàn)網(wǎng)。若映射：BE→

PT滿足條件（1）對于(B)P,(E)T,x,yBE：(x,y)G

→((x),(y))F

（2）eE：(?e)=?(e)，(e?)=(e)?

則稱定義了N到N的一個映射，記為：N

→N。定義3.13.設PN=(N,M0)=(P,T;F,M0)為一個Petri網(wǎng)，N=(B,E;G)為一個出現(xiàn)網(wǎng)。如果：N

→N滿足條件（1）b1,b2B，b1≠b2

：(b1)=(b2)→

?b1

≠

?b2

b1?

≠

b2?

（2）pP：|{b|(b)=p

?b=

Φ}|M0(p)

則稱(N,

)為PN的一個進程（process）。Petri網(wǎng)進程定義3.12.設N=(P,T;F)為一個網(wǎng)，Petri網(wǎng)進程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網(wǎng)進程p1t1t2p4t5p3p2t3t4p5e4Petri網(wǎng)進程定義3.14.設PN=(N,M0)=(P,T;F,M0)為一個Petri網(wǎng)，N=(B,E;G)為一個出現(xiàn)網(wǎng)。如果：N

→N滿足條件（1）b1,b2B，b1≠b2

：(b1)=(b2)→(?b1

≠

?b2?b1

=

?b2=

Φ)(b1?

≠

b2?b1?

=

b2?

=

Φ)

（2）pP：|{b|(b)=p

?b=

Φ}|=

M0(p)

則稱(N,

)為PN的一個滿進程（process）。定理3.5.設(N,

)為Petri網(wǎng)PN=(N,M0)=(P,T;F,M0)的一個滿進程，則對的任一個s-切u，都存在MR(M0)

使得

|{b|bu

(b)=p}|=

M

(p)

簡記為(u)=M。Petri網(wǎng)進程定義3.14.設PN=(N,M0)=(Petri網(wǎng)進程證.令u0={b|?b=Φ}，顯然u0是N的一個s-切，且(u0)=M0。設u為N的任一個s-切。顯然u0

u，記

E(u0,u)={eE|b0u0,bu:(b0,e)G+(e,b)G+}

下面對|E(u0,u)|用數(shù)學歸納法證明定理的結(jié)論。當|E(u0,u)|=0時，顯然u=u0，從而(u0)=M0R(M0)。設對|E(u0,u)|=k的任一個s-切u，都有MR(M0)使得

(u)=M。那么當|E(u0,u)|=k+1時，易知存在N的一個s-切u1，使得

u0

u1u（從而E(u0,u1)E(u0,u)），且|E(u0,u1)|=k。設E(u0,u)-E(u0,u1)={e}，則有?eu1，(u1-?e)e?=u(u1)=M1，(e)=t，因此有M1[t>。設M1[t>M，則(u)=M。Petri網(wǎng)進程證.令u0={b|?b=Φ}，顯然在簡單有向圖中，若任何兩個節(jié)點間是相互可達的，則稱是強連通圖；若任何兩個節(jié)點之間至少從一個節(jié)點到另一個節(jié)點是可達的，則稱是單向連通圖或單側(cè)連通圖；若在圖中略去邊的方向，將它看成無向圖后，圖是連通的，則稱該圖是弱連通圖。簡單有向圖中擁有附連通性質(zhì)的最大子圖就是強分圖。在簡單有向圖中，第三部分Petri網(wǎng)的分析方法第三部分Petri網(wǎng)的分析方法提綱可達標識圖與可覆蓋性樹關(guān)聯(lián)矩陣與狀態(tài)方程Petri網(wǎng)語言Petri網(wǎng)進程提綱可達標識圖與可覆蓋性樹可達標識圖與可覆蓋性樹對于有界Petri網(wǎng)，其可達標識集R(M0)是一個有限集合，因此可以以R(M0)作為頂點集，以標識之間的直接可達關(guān)系為弧集構(gòu)成一個有向圖，稱為Petri網(wǎng)的可達標識圖（reachablemarkinggraph）。定義3.1.設PN=(P,T;F,M0)為一個有界Petri網(wǎng)。PN的可達標識圖定義為一個三元組RG(PN)=(R(M0),E,L)，其中

E={(Mi,Mj)|Mi,MjR(M0),tkT:Mi[tk>Mj}L:E→T，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可達標識圖與可覆蓋性樹對于有界Petri網(wǎng)，其可達標識集R(可達標識圖與可覆蓋性樹通過可達標識圖RG(PN)可以分析有界Petri網(wǎng)PN的各種性質(zhì)。定理3.1.

對任意Mi,MjR(M0)，Mj是從Mi可達的當且僅當在RG(PN)中，從Mi到Mj存在一條有向路。推論3.1.

在RG(PN)中，從M0到每個結(jié)點都有一條有向路。推論3.2.

MR(M0)是PN的一個死標識當且僅當在RG(PN)中，M是一個終端標識。定理3.2.

設pjP，在Petri網(wǎng)PN中pj的界B(pj)等于RG(PN)中各個頂點向量的第j個分量的最大值。推論3.3.PN是安全的當且僅當RG(PN)中每個頂點的向量都是0-1向量。可達標識圖與可覆蓋性樹通過可達標識圖RG(PN)可以分析有界可達標識圖與可覆蓋性樹定理3.3.

有界Petri網(wǎng)PN是活的當且僅當在RG(PN)中，從頂點M0出發(fā)的每條有向路都走入一個強連通子圖，而且在每個這樣的強連通子圖中，每個tT至少是一條有向弧的旁標。定理3.4.

有界Petri網(wǎng)PN的兩個變遷t1和t2處于公平關(guān)系的充分必要條件是在RG(PN)的每條有向回路C中，t1是其中的一條弧的旁標當且僅當t2也是其中一條弧的旁標。定理3.5.PN是公平Petri網(wǎng)的充分必要條件是在RG(PN)的每條有向回路C中，每個tT都至少是C中一條弧的旁標。定理3.3、3.4和3.5在無界Petri網(wǎng)中還成立嗎？？可達標識圖與可覆蓋性樹定理3.3.有界Petri網(wǎng)PN是活可達標識圖與可覆蓋性樹若PN不是有界網(wǎng)，則R(M0)是一個無限集合，無法畫出PN的可達標識圖。為了用有限形式表達一個有無限個狀態(tài)的系統(tǒng)的運行情況，引入一個表示無界量的符號。具有下述性質(zhì)：（1）對任意正整數(shù)n：>n，n=

（2）當庫所pj中的標識數(shù)在Petri網(wǎng)的運行過程中趨向于無限增長時，就把標識向量中的第j個分量改為，以此覆蓋所有這類標識。通過引入，就可以用有限樹來反映無界Petri網(wǎng)的運行情況，稱該有限樹為Petri網(wǎng)PN的可覆蓋性樹（coverabilitytree），記為CT(PN)?？蛇_標識圖與可覆蓋性樹若PN不是有界網(wǎng)，則R(M0)是一個無可達標識圖與可覆蓋性樹算法3.1.Petri網(wǎng)可覆蓋性樹的構(gòu)造算法輸入：PN=(P,T;F,M0)

輸出：CT(PN)

算法步驟：

Step0：以M0作為CT(PN)的根結(jié)點，并標之以“新”；

Step1：While存在標注為“新”的結(jié)點Do

任選一個標注為“新”的結(jié)點，設為M；

Step2：If從M0到M的有向路上有一個結(jié)點的標識等于MThen

把M的標注改為“舊”，返回Step1；

Step3：IftT:M[t>Then

把M的標注改為“端點”，返回Step1Step4：For每個滿足M[t>的tTDo4.1：計算M[t>M’中的M’；

4.2：If從M0到M的有向路上存在M’’使M’’<M’Then

找出使M’’(pj)<M’(pj)的分量j，把M’的第j個分量改為；

4.3：在CT(PN)中引入一個“新”結(jié)點M’，從M到M’畫一條有向弧，并把此弧旁標以t；

Step5：擦去結(jié)點M的“新”標注，返回Step1?？蛇_標識圖與可覆蓋性樹算法3.1.Petri網(wǎng)可覆蓋性樹的可達標識圖與可覆蓋性樹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)新新新新新舊舊新端點可達標識圖與可覆蓋性樹p1p2t1t2p4t3t4p3M0可達標識圖與可覆蓋性樹定理3.1.PN是有界Petri網(wǎng)當且僅當（按算法3.1構(gòu)造的）CT(PN)中，每個結(jié)點的標識向量都不含有分量。對有界Petri網(wǎng)PN，按照算法3.1構(gòu)造出來的樹結(jié)構(gòu)稱為PN的可達性樹（reachabilitytree），記為RT(PN)。定義3.2.設CT(PN)為Petri網(wǎng)的可覆蓋性樹。若將CT(PN)中標識向量相同的結(jié)點合并在一起，便得到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可達標識圖與可覆蓋性樹定理3.1.PN是有界Petri網(wǎng)當提綱可達標識圖與可覆蓋性樹關(guān)聯(lián)矩陣與狀態(tài)方程Petri網(wǎng)語言Petri網(wǎng)進程提綱可達標識圖與可覆蓋性樹關(guān)聯(lián)矩陣與狀態(tài)方程網(wǎng)的結(jié)構(gòu)可以用一個矩陣來表示，從而可以引入線性代數(shù)的方法對Petri網(wǎng)進行分析。定義3.3.設PN=(P,T;F,M0)為一個Petri網(wǎng)。P={p1,p2,,pm}

，T={t1,t2,,tn}，則網(wǎng)N=(P,T;F)可以用一個n行m列矩陣

A=[aij]nm

（3.1）來表示，稱A為PN（N）的關(guān)聯(lián)矩陣（incidencematrix）。其中關(guān)聯(lián)矩陣與狀態(tài)方程網(wǎng)的結(jié)構(gòu)可以用一個矩陣來表示，從而可以引入關(guān)聯(lián)矩陣與狀態(tài)方程PN的輸出矩陣PN的輸入矩陣行向量列向量標識M關(guān)聯(lián)矩陣與狀態(tài)方程PN的輸出矩陣關(guān)聯(lián)矩陣與狀態(tài)方程p1p2t1t2p4t3t4p3p1p2t1t2p4t3t4p3A-=0100100000110110p1p2t1t2p4t3t4p3A+=1000011010000001A=A+-A-

=p1p2t1t2p4t3t4p31-100-111010-1-10-1-11關(guān)聯(lián)矩陣與狀態(tài)方程p1p2t1t2p4t3t4p3p1p2t關(guān)聯(lián)矩陣與狀態(tài)方程引理3.1.設PN=(P,T;F,M0)為一個Petri網(wǎng)。A為PN的關(guān)聯(lián)矩陣，tiT，則M[ti>的充分必要條件是引理3.2.設PN=(P,T;F,M0)為一個Petri網(wǎng)。A為PN的關(guān)聯(lián)矩陣，如果M[ti>M’，則有定理3.2.設PN=(P,T;F,M0)為一個Petri網(wǎng)。A為PN的關(guān)聯(lián)矩陣，若MR(M0)，則存在非負整數(shù)的n維向量X，使得

上式稱為Petri網(wǎng)的狀態(tài)方程（stateequation）。狀態(tài)方程是M從M0可達的一個必要條件，而非充分條件。關(guān)聯(lián)矩陣與狀態(tài)方程引理3.1.設PN=(P,T;F,M0關(guān)聯(lián)矩陣與狀態(tài)方程證：關(guān)聯(lián)矩陣與狀態(tài)方程證：變遷發(fā)生序列與Petri網(wǎng)語言Petri網(wǎng)進行分析的另一種方法是考察網(wǎng)系統(tǒng)中所有可能發(fā)生的變遷序列以及這些序列構(gòu)成的集合的性質(zhì)。一個字母表上滿足某些特定條件的字符串的集合，稱為該字母表上的一個語言。將Petri網(wǎng)的變遷集T看作一個字母表，或者給出變遷集到某個字母表上的一個映射，那么該Petri網(wǎng)所有可能發(fā)生的變遷序列（或其映射）的集合就是T（或）上的一個語言。變遷發(fā)生序列與Petri網(wǎng)語言Petri網(wǎng)進行分析的另一種方變遷發(fā)生序列與Petri網(wǎng)語言定義3.4.設PN=(P,T;F,M0)為一個Petri網(wǎng)。:T→為標注函數(shù)，QtR(M0)。令

L={()*|T*:M0[>M,MQt}L’={()*|(T*:M0[>M)(M’Qt，MM’)}

（1）若Qt是預先給定R(M0)的一個子集，則稱L為PN產(chǎn)生的L-型語言；L’稱為PN產(chǎn)生的G-型語言。（2）若Qt={MR(M0)|tT:M[t>}，則稱L為PN產(chǎn)生的T-型語言。（3）若Qt=

R(M0)

，則稱L為PN產(chǎn)生的P-型語言。變遷發(fā)生序列與Petri網(wǎng)語言定義3.4.設PN=(P,T;變遷發(fā)生序列與Petri網(wǎng)語言定義3.5.設PN=(P,T;F,M0)為一個Petri網(wǎng)。L是PN產(chǎn)生的L-型（G-型，T-型，P-型）語言。對于標注函數(shù):T→：（1）若=T，且tT:(t)=t，則稱L是PN產(chǎn)生的L-型（G-型，T-型，P-型）無標注語言，記為Lf（Gf，Tf，Pf）（2）若tT:(t)（表示空串），則稱L是PN產(chǎn)生的L-型（G-型，T-型，P-型）無空標注語言，記為L（G，T，P）；否則稱L是PN產(chǎn)生的L-型（G-型，T-型，P-型）含空標注語言，記為L（G

，T

，P

）。變遷發(fā)生序列與Petri網(wǎng)語言定義3.5.設PN=(P,T;變遷發(fā)生序列與Petri網(wǎng)語言設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}變遷發(fā)生序列與Petri網(wǎng)語言設Qt={M1}，則Lf(變遷發(fā)生序列與Petri網(wǎng)語言終止符集標注無標注類無空標注類含空標注類L-型Lf

LLG-型GfGGT-型TfTTP-型PfPP變遷發(fā)生序列與Petri網(wǎng)語言終止符集標注無標注類無空標注類變遷發(fā)生序列與Petri網(wǎng)語言RLPNLCFLCSL每種正規(guī)語言（RL）都是Petri網(wǎng)語言（PNL）每種Petri網(wǎng)語言都是上下文有關(guān)語言（CSL）Petri網(wǎng)語言類同上下文無關(guān)語言類（CFL）是兩個相交但互不包含的語言類PNL同Chomsky體系中各型語言的關(guān)系變遷發(fā)生序列與Petri網(wǎng)語言RLPNLCFLCSL每種正規(guī)變遷發(fā)生序列與Petri網(wǎng)語言定義3.6.設PN=(P,T;F,M0)為一個Petri網(wǎng)。稱

L0(PN)={T*|M0[>M}

或L0(PN)={T*|MR(M0):M0[>M}

為PN所確定的P-型無標注語言。簡稱為PN所確定的語言。L0(PN)是Petri網(wǎng)PN從初始標識M0出發(fā)的一切可發(fā)生的變遷序列的集合。由于M0R(M0)，所以總有L0(PN)。變遷發(fā)生序列與Petri網(wǎng)語言定義3.6.設PN=(P,T;變遷發(fā)生序列與Petri網(wǎng)語言設為一個串，L為一個語言，記

Pref()={x|y:xy=}Suff()={x|y:yx=}Pref(L)={x|L:xPref()}Suff(L)={x|L:xSuff()}定義3.7.設L為一種語言，如果

Pref(L)=L

則稱L為一種前綴語言。定理3.3.Petri網(wǎng)PN=(P,T;F,M0)所確定的語言L0(PN)是一種前綴語言，即

Pref(L0(PN))=L0(PN)變遷發(fā)生序列與Petri網(wǎng)語言設為一個串，L為一個語言，記變遷發(fā)生序列與Petri網(wǎng)語言在形式語言理論中，Pumping引理是正規(guī)語言和上下文無關(guān)語言的一個重要性質(zhì)。定理3.4.設PN=(P,T;F,M0)為一個有界Petri網(wǎng)，L0(PN)。如果|||R(M0)|，則可寫成=xyz的形式，其中x,y,zT*,|xy||R(M0)|且|y|1，使得對任意非負整數(shù)i，都有xyizL0(PN)。注：RG(PN)可看作是有限自動機的一個圖形表示。推論3.1.設PN=(P,T;F,M0)為一個有界Petri網(wǎng)，若L0(PN)，使得|||R(M0)|，則L0(PN)是一個無限集。變遷發(fā)生序列與Petri網(wǎng)語言在形式語言理論中，Pumpin提綱可達標識圖與可覆蓋性樹關(guān)聯(lián)矩陣與狀態(tài)方程Petri網(wǎng)語言Petri網(wǎng)進程提綱可達標識圖與可覆蓋性樹Petri網(wǎng)進程Petri網(wǎng)語言不能很好地反映系統(tǒng)中的并發(fā)行為。為此網(wǎng)論中引入了Petri網(wǎng)進程的概念。Petri網(wǎng)進程的概念是建立在出現(xiàn)網(wǎng)（occurrencenet）和網(wǎng)映射等概念基礎上的。定義3.8.設N=(P,T;F)為一個網(wǎng)，定義

稱F+為流關(guān)系F的傳遞閉包。id表示自反關(guān)系。定義3.9.設N=(B,E;G)為一個網(wǎng)。如果（1）bB：|?b|1|b?|1

（2）

x,yBE：(x,y)G+→(y,x)G+

則稱N為一個出現(xiàn)網(wǎng)，其中G+表示流關(guān)系G的傳遞閉包。出現(xiàn)網(wǎng)中沒有情態(tài)（標識）的概念，它是通過流關(guān)系來描述系統(tǒng)中事件發(fā)生的軌跡。Petri網(wǎng)進程Petri網(wǎng)語言不能很好地反映系統(tǒng)中的并發(fā)行Petri網(wǎng)進程定義3.10.設N=(B,E;G)為一個出現(xiàn)網(wǎng)，lBE。如果

x,yl：(x,y)G+(y,x)G+

則稱l為N的一個線集。若l是N的一個線集，且任意l’l都不是N的線集，則稱l為N的一條線。定義3.11.設N=(B,E;G)為一個出現(xiàn)網(wǎng)，uBE。如果

x,yu：(x,y)G+

(y,x)G+

則稱u為N的一個切集。若u是N的一個切集，且任意u’u都不是N的切集，則稱u為N的一個切。若u是N的一個切，且uB，則稱u為N的一個s-切。設u1,u2為N的兩個切，如果xu1，yu2

：(x,y)G*

，則記為u1

u2。事件e1和e2存在并發(fā)關(guān)系當且僅當N中存在一個切u，使得e1u且e2u事件e1和e2存在固定的順序關(guān)系當且僅當N中存在一條線l，使得e1l且e2lPetri網(wǎng)進程定義3.10.設N=(B,E;G)為一個出現(xiàn)Petri網(wǎng)進程定義3.12.設N=(P,T;F)為一個網(wǎng)，N=(B,E;G)為一個出現(xiàn)網(wǎng)。若映射：BE→

PT滿足條件（1）對于(B)P,(E)T,x,yBE：(x,y)G

→((x),(y))F

（2）eE：(?e)=