Petri网语言的Pumping引理

• 作者: 刘关俊 蒋昌俊
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: Petri网 语言 正规语言 Pumping引理
• 年，卷（期）: 2006,（2）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 274-278
• 页数: 5页
• 分类号: TP393
• 字数: 5108字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.2006.02.011

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	蒋昌俊	同济大学计算机系	93	1492	18.0	36.0
2	刘关俊	山东科技大学信息学院	5	29	2.0	5.0