资源描述：
《Petri 网 基本概念和分析方法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、北京师范大学信息科学学院知识工程研究中心Petri网:基本概念和分析方法+记号:N={0,1,2,…},N={0,1,2,…}.一.基本概念一个Petri网由五个部分组成PN=(P,T,F,W,M0),其中:µP是位置(place)的有限集合;µT是迁移(transition)的有限集合;µP…T=«,P»T∫«;µFŒ(PäT)»(PäT)是有向弧的集合;+µw:FöN是弧的权函数;µM0:PöN是初始标记(初始状态).注.不带初始状态的Petri网记为N=(P,T,F,W),带有初始状态M0的Petri网则记为(N,M0).若PN是一个Petri网,则映射
2、M:PöN称为一个状态.对pœP,若M(p)=k,则称位置p标记有k个符号(token).Petri网的状态状态可以用向量来表示:若P={p1,p2,…,pm},且M(pi)=ki,则写M=(k1,k2,…,km).若弧(p,t)œFŒPäT,则称p是t的输入位置;而若弧(t,p)œFŒTäP,则称p是t的输出位置.对(p,t)œF或(t,p)œF,w(p,t)或w(t,p)称为对应弧的权.迁移(点火)法则.设M:PöN是Petri网(N,M0)的一个状态,tœT.(1)迁移t称为在状态M下使能的(enable),如果对t的任何输入位置p,有:M(p)¥w(p
3、,t).£(2)设迁移t在状态M下为使能的,M是如下定义的状态:对pœP,M(p)-w(p,t)若p是t的输入位置£M(p)=M(p)+w(t,p)若p是t的输出位置M(p)若p为其它位置££则称t被点火(击发),且系统从状态M迁移到状态M,记为MtM.例1.化学反应2H2+O2ö2H2O的Petri网表示.1北京师范大学信息科学学院知识工程研究中心图1.1.Petri网模拟若一个Petri网中的每个迁移都只有一个输入位置和一个输出位置,则称该网是确定的或称为一个状态机.若每个位置恰好有一条进入弧和一条发出弧,则称该网是一个标记图(markedgraph).例
4、2.一个饮料贩卖机的Petri网表示.这是一个状态机.图1.2.饮料贩卖机的Petri网模拟.若存在某个位置p,p是至少两个迁移的输入位置,则称此网为非确定的,或者根据特定的应用领域,称为冲突,决策或者选择等.图1.3.冲突,决策,选择两个迁移t1,t2œT称为并发的,如果t1,t2是因果独立的,即两者都可以先后点火或者并行点火.例3.迁移t2,t3是并发的,而此网是一个标记图.2北京师范大学信息科学学院知识工程研究中心图1.4.并发既有并发迁移又有冲突迁移的Petri网称为混合型的.并发迁移与其它迁移可以是对称的(同时冲突),也可以是非对称的.(a)t1,t
5、2是并发的,而且都与t3冲突.(b)t1,t2是并发的,且若t2在t1前点火,则t1与t3冲突.图1.5.对称与非对称Petri网的可达图是其可能状态和使能迁移关系的图表示.(a)一个Petri网(b)上述网的可达图图1.6.可达图3北京师范大学信息科学学院知识工程研究中心二.Petri网的行为2.1可达性设(N,M0)是一个Petri网.一个点火序列s=t1…tn是状态和迁移的序列:M0t1M1t2M2…tnMn.(N,M0)的所有可能的点火序列的集合记为L(N,M0)或L(M0).若s=t1…tnœL(M0),且M0t1M1t2M2…tnMn,则称状态Mn
6、可由M0通过s到达,并记为M0[s>Mn.所有可从M0到达的状态的全体记为R(N,M0)或R(M0).Petri网可达性问题.对(N,M0)的任何状态M,是否MœR(M0)?2.2有界性设kœN.Petri网(N,M0)称为k-有界的,如果对任何位置p和状态MœR(M0),M(p)§k.(N,M0)称为安全的,如果它是1-有界的.2.3活性Petri网(N,M0)称为活性的,如果在任何状态MœR(M0)下,通过适当的点火序列后,每个迁移最终都可以被点火.在活性Petri网中,无论怎样选取点火序列,都保证不会出现死锁.例如,下面的通信协议的Petri网表示是活性
7、的:图2.1.活性网活性概念可以分层.设t是Petri网(N,M0)中的一个迁移.则:(1)若对L(M0)中任何点火序列,t都不能被点火,则称t是L0-活性的(死的);4北京师范大学信息科学学院知识工程研究中心(2)若对L(M0)中的某个点火序列,t至少能被点火一次,则称t是L1-活性的(潜在可点火的);(3)若对任何kœN,关于L(M0)中的某个点火序列,t至少能被点火k次,则称t是L2-活性的;(3)若在L(M0)中的某个点火序列中,t可以不定地出现,则称t是L3-活性的;(4)若对每个MœR(M0),t都是L3-活性的,则称t是L4-活性的(活性的).对
8、k=0,1,2,3,4,Petri网(
