资源描述：
《基于petri网语言的程序设计》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、http://www.paper.edu.cn基于Petri网语言的程序设计112王燕，卢慧，赵锦明1内蒙古大学计算机学院，内蒙古呼和浩特（010021）2内蒙古呼和浩特计生委，内蒙古呼和浩特（010050）E-mail：cswy@imu.edu.cn摘要：本文采用一种Petri网语言的同步合成的原理，提出了计算机复杂程序设计流程的一种新的设计思想。并且利用Petri网语言给出了系统合成时的死锁分析和系统设计时的效率分析以及整个设计流程。关键词：Petri网，语言，设计流程中图分类号：TP3931.引言计算机程序设计是一个复杂的任务设计过程，通常需要分解成多个子系统
2、来进行分析设计，而这类系统又经常伴随并发、竞争等情况。Petri网分析方法被认为是系统并发分析的有效工具。与其他工具相比，Petri网的优势在于它的图形建模的直观性和理论分析的严谨性，因此Petri网在大型系统建模分析中备受关注。所以用Petri网对计算机程序设计进行建模分析是一种有效的方法。以往Petri网建模分析的方法是用Petri网直接模拟一个要设计的系统，然后利用Petri网的一些分析方法如状态方程法、可达图法等对系统模型进行分析。这对复杂的计算机程序设计来说有很大的局限性,首先计算机程序复杂庞大，多任务服务需要分解设计，各个服务进程经常会产生冲突，最终子系
3、统的合成可能会造成总系统的死锁，从而使总系统的活性无法得到保证。本文基于Petri网语言以及Petri网的同步合成原理，从简单子系统的设计分析开始，然后合成为复杂系统，并通过Petri网语言来判断合成模型的活性，并通过增加控制系统来保证复杂系统的活性，然后通过对设计系统进行性能指标的定量分析来判断设计效率。本文通过一个信息服务系统为例说明了分析和设计过程，并给出了设计流程图。2.基本理论[1]Petri网是由库所、变迁和连接库与变迁间关系的有向弧所组成的一种有向图。定义1：一个四元组PN=(P，T，F，M0)被称为Petri网，如果满足如下条件，(1)P∪T≠Ф;(
4、2)P∩T=Ф;(3)F∈(T×P)∪(P×T);(4)dom(F)∪cod(F)=P∪T;其中P是位置集，T是变迁集，F是有向弧集，M0是P的初始标志。为了描述用Petri网分析的依据，下面就给出一种Petri网描述语言。*定义2：设Petri网PN=(P，T，F，M0)，若L(PN)={a
5、aÎTΛM0[a>},则称L(PN)为PN*的语言。其中T是包含T的变迁集，Λ是合成运算，M0[a>表示在标志M0下的最小字符串单位，它是Petri网子统变迁引发过程的描述。定义3：设Petri网PN=(P，T，F，M0)，称PN为活的，当且仅当"tÎT，"MÎR(M0)，$
6、M’ÎR(M),使得M’[t>,即t是M’下的最小变迁集。~ÍT是一种语言，若有L={a
7、aÎLÙ$a’ÎT*定义4：设L,àa·a’ÎL}，~~L={a
8、aÎLÙ$a’ÎT,àa·a’ÎLÙJ(a’)=T}，其中J(a’)表示a’中所有字符集合，-1-http://www.paper.edu.cn式中采用的积是笛卡儿积，则称L1、L2分别是语言L的前缀和强前缀语言。定理1：设Petri网PN=(P，T，F，M0)，则PN为活的充分必要条件是L(PN1)=L(PN2)，其中L(PN)见定义4。定义5：设有两个Petri网PN2=(P2，T2，F2，M02)和PN1=
9、(P1，T1，F1，M01)，令PN=(P，T，F，M0)，使得:(1)P=P1∪P2,P1∩P2=Ф;(2)T=T1∪T2,T1∩T2≠Ф;(3)M(P1)=M01(P1)ΛM(P2)=M02(P2);(4)M(P2)=M02(P2)ΛM(P1)=M01(P1);则称PN是å1与å2同步合成网，记做PN=PN1qPN2,L(PN1)和L(PN2)分别是PN1和PN2l1的语言。建立映射λ,有L(PN)¾¾®L(PN1)，i=1,2,L(PN)是PN的语言，使得"aÎL(PNi)，都有λi(a)为在a中删去所有PNiÅ1至PNi中的字符所得到的字符串，这里iÅ1=（
10、imod2）+1,i=1,2。则称λi为,L(PN)到L(PNi)的投影函数。λi-1记做λi逆映射。定理2：设Petri网PNi(Pi，Ti，Fi，M0i)，i=1,2,PN=PN1qPN2，则L(PN)=λ1-1(L(PN1))Çλ2-1(L(PN1))。*证明："aÎL(PN),设a=ti1ti2...tikÎT则根据定义2和定义3，$M0,M1,M2,ΛMkÎR(M0)，*使得有激发过程M0[ti1>M1[ti2>M2ΛMk-1[tikÎT>Mk，再根据定义4知P1ÇP2=Ф,P=P1ÈP2，MTTe,a2ße,其中e为空串，然后分别考虑如下情况：0=(
