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

The Pumping Lemma for Context-free Language of Petri Net

作　　者：张继军[1] 吴哲辉[2] 

机构地区：[1]山东农业大学信息学院,山东泰安271018 [2]山东科技大学信息学院,山东青岛266510

出　　处：《小型微型计算机系统》2008年第4期698-702,共5页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(60673053)资助

摘　　要：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.

关 键 词：Pumping引理 语言 PETRI网 上下文无关语言 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]