| 《计算机学报》文章摘要 全文下载 | |
| 文章题目 | Petri网语言的Pumping引理 |
| 作者 | 蒋昌俊1) 刘关俊2) |
| 作者单位 | 1)(同济大学计算机系 上海 200092) 2)(山东科技大学信息学院 青岛 266510) |
| 发表年份 | 2006 |
| 发表月份 | 2期(274—278) |
| 文章摘要 | 摘要 Petri网语言是Petri网理论的重要组成部分，也是系统行为分析的一种重要的工具.Petri网语言的Pumping引理反映了Petri网语言的共性，可用来证明某些语言不是Petri网语言.已经证明，当一个Petri网语言可被某个有界Petri网产生时，此语言是正规语言，因此，正规语言的Pumping引理对此语言是有效的，但正规语言的Pumping引理并不适用于所有的Petri网语言.文中给出了一种Petri网语言的Pumping引理，证明其对任意无空标注的Petri网语言都有效，并且正规语言的Pumping引理是此引理的一种特殊形式.利用此Pumping引理可以证明某些语言是不能由Petri网产生的. 关键词 Petri网；语言；正规语言；Pumping引理 中图法分类号 TP393 |