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

摘要：

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

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

所属期刊栏目：29

分类号：TP18(自动化基础理论)

资助基金：国家自然科学基金60673053

在线出版日期：2008-05-26（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：698-702