Petri网语言的Pumping引理  

The Pumping Lemma of Petri Net Language

作　　者：蒋昌俊[1] 刘关俊[2] 

机构地区：[1]同济大学计算机系,上海200092 [2]山东科技大学信息学院,青岛266510

出　　处：《计算机学报》2006年第2期274-278,共5页Chinese Journal of Computers

基　　金：国家自然科学基金项目(60125205;90412013;60473094;60534060);国家"九七三"重点基础研究发展规划项目基金(2003CB316902;2004CB318001-03);上海市优秀学科带头人计划项目基金(04XD14016);上海市基础研究重点项目基金(03JC14071;05JC14063)资助

摘　　要：Petri网语言是Petri网理论的重要组成部分,也是系统行为分析的一种重要的工具.Petri网语言的Pumping引理反映了Petri网语言的共性,可用来证明某些语言不是Petri网语言.已经证明,当一个Petri网语言可被某个有界Petri网产生时,此语言是正规语言,因此,正规语言的Pumping引理对此语言是有效的,但正规语言的Pumping引理并不适用于所有的Petri网语言.文中给出了一种Petri网语言的Pumping引理,证明其对任意无空标注的Petri网语言都有效,并且正规语言的Pumping引理是此引理的一种特殊形式.利用此Pumping引理可以证明某些语言是不能由Petri网产生的.Petri net language is both an important component of Petri net theory and a good tool for analyzing behavior of a system. The Pumping Lemma of Petri net language reflects some commonness of Petri net language and can be used to prove that some languages is not Petri net language. A Petri net language L, which is produced by a bounded Petri net, has been proved to be a regular language. So the Pumping Lemma of regular language is effective to L. But the Pumping Lemma of regular language is not applicable for any Petri net language. This article gives a Pumping Lemma of Petri net language which is proved to be effective to all Petri net languages without empty-label and the Pumping Lemma of regular languages actually is a special format of the Lemma. By the Lemma, this paper proofs some languages not be produced by any Petri net.

关 键 词：PETRI网 语言 正规语言 Pumping引理 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]