摘要
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.
出处
《计算机学报》
EI
CSCD
北大核心
2006年第2期274-278,共5页
Chinese Journal of Computers
基金
国家自然科学基金项目(60125205
90412013
60473094
60534060)
国家"九七三"重点基础研究发展规划项目基金(2003CB316902
2004CB318001-03)
上海市优秀学科带头人计划项目基金(04XD14016)
上海市基础研究重点项目基金(03JC14071
05JC14063)资助
