| Petri网语言的Pumping引理 |
| |
| 引用本文： | 蒋昌俊,刘关俊.Petri网语言的Pumping引理[J].计算机学报,2006,29(2):274-278. |
| |
| 作者姓名： | 蒋昌俊 刘关俊 |
| |
| 作者单位： | 1. 同济大学计算机系,上海,200092
2. 山东科技大学信息学院,青岛,266510 |
| |
| 基金项目： | 中国科学院资助项目;科技部科研项目;上海市优秀学科带头人项目;上海市重点基础研究项目 |
| |
| 摘 要： | Petri网语言是Petri网理论的重要组成部分，也是系统行为分析的一种重耍的工具．Petri网语言的Pumping引理反映了Petri网语言的共性，可用来证明某些语言不是Petri网语言，已经证明，当一个Petri网语言可被某个有界Petri网产生时，此语言是正规语言，因此，正规语言的Pumping引理对此语言是有效的，但正规语言的Pumping引理并小适用于所有的Petrl网语言．文中给出了一种Petri网语言的Pumping引理，证明其对任意无空标注的Petri网语言都有效，并且＋正规语言的Pumping引理是此引理的一种特殊形式．利用此Pumping引理可以证明某些语言是不能由Petri网产生的。
|
| 关 键 词： | Petri网 语言 正规语言 Pumping引理 |
| 收稿时间： | 2005-02-28 |
| 修稿时间： | 2005-02-282005-11-01 |
The Pumping Lemma of Petri Net Language |
| |
| JIANG Chang-Jun,LIU Guan-Jun.The Pumping Lemma of Petri Net Language[J].Chinese Journal of Computers,2006,29(2):274-278. |
| |
| Authors: | JIANG Chang-Jun LIU Guan-Jun |
| |
| Affiliation: | 1.Department of Computer, Tangji University, Shanghai 200092;2.College of Information, Shandong University of ,Science and Technology, Qingdao 266510 |
| |
| Abstract: | 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. |
| |
| Keywords: | Petri nets language regular language Pumping lemma |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
