上下文无关Petri网语言的Pumping引理

The Pumping Lemma for Context-free Language of Petri Net

Petri网语言可分为正规Petri网语言、上下文无关Petri网语言和Petri网语言三类,Pumping引理反映了一类语言的共性.对于正规Petri网语言类和Petri网语言类都已给出了其相应的Pumping引理,而对于上下文无关Petri网语言类的Pumping引理却一直未给出.本文通过分析上下文无关Petri网语言的结构性质,给出了上下文无关Petri网语言的Pumping引理,并且正规Petri网语言的Pumping引理是上下文无关Petri网语言的Pumping引理的一种特殊形式,而上下文无关Petri网语言的Pump-ing引理又是Petri网语言Pumping引理的一种特殊形式,从而完整地解决了三类Petri网语言Pumping引理以及它们之间的关系.

There are three language classes for language of Petri net, which are regular language of Petri net, context-free language of Petri net and language of Petri net. The Pumping lemma of a language class reflects some commonness of the language, the Pumping lemmas for regular language of Petri net and for language of Petri net have been given,but the Pumping lemmas for context-free language of Petri net had not been given up to now. The structural feature of context-free language of Petri net is analyzed and the Pumping lemma for context-free language of Petri net is given in this paper. The Pumping lemmas for regular language of Petri net is a special format of the Pumping lemmas for context-free language of Petri net, and the Pumping lemmas for context-free language of Petri net is a special format of language of Petri net.