Chinese Journal of Computers   Full Text
Title	The Pumping Lemma of Petri Net Language
Authors	JIANG Chang-Jun1) LIU Guan-Jun2)
Address	1)(Department of Computer, Tongji University, Shanghai 200092) 2)(College of Information, Shandong University of Science and Technology, Qingdao 266510)
Year	2006
Issue	No.2(264—278)
Abstract &   Background	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 background In the theory of formal language, only for regular language and context-free language there exist pumping lemmas. The pumping lemma of regular language reflects some commonness of regular languages and can be used to prove certain languages not regular. The pumping lemma of context-free language is so too. It has been proved that the set of all regular languages is properly contained in the set of all Petri net languages. And the set of all context-free languages and the set of all Petri net languages are intersecting but not contained mutually. We discovered that for Petri net language there also exists pumping lemma. The pumping lemma reflects some commonness of Petri net language and can be used to prove that certain languages are not produced by any Petri net.