Petri网语言的Pumping引理

被引：12

作者：

蒋昌俊 ^{[1
]}

刘关俊 ^{[2
]}

机构：

[1] 同济大学计算机系

[2] 山东科技大学信息学院

来源：

计算机学报 | 2006年 / 02期

关键词：

Petri网; 语言; 正规语言; Pumping引理;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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

引用

页码：274 / 278

页数：5

共 6 条

[1] PN语言识别器 [J].