Petri网语言的Pumping引理

摘要：

Petri网语言是Petri网理论的重要组成部分,也是系统行为分析的一种重要的工具.Petri网语言的Pumpmg引理反映了Petri网语言的共性,可用来证明某些语言不是Petri网语言.已经证明,当一个Petri网语言可被某个有界Petri网产生时,此语言是正规语言,因此,正规语言的Pumping引理对此语言是有效的,但正规语言的Pumping引理并不适用于所有的Petri网语言.文中给出了一种Petri网语言的Pumping引理,证明其对任意无空标注的Petri网语言都有效,并且正规语言的Pumping引理是此引理的一种特殊形式.利用此Pumping引理可以证明某些语言是不能由Petri网产生的.

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

所属期刊栏目：29

分类号：TP393(计算技术、计算机技术)

资助基金：中国科学院资助项目60125205;90412013;60473094;60534060;科技部科研项目2003CB316902;2004CB3t8001-03;上海市优秀学科带头人项目04XD14016;上海市重点基础研究项目03JC14071;05JC14063

在线出版日期：2006-04-06（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：274-278