Petri网语言的Pumping引理

Petri网语言是Petri网理论的重要组成部分,也是系统行为分析的一种重要的工具.Petri网语言的Pumping引理反映了Petri网语言的共性,可用来证明某些语言不是Petri网语言.已经证明,当一个Petri网语言可被某个有界Petri网产生时,此语言是正规语言,因此,正规语言的Pumping引理对此语言是有效的,但正规语言的Pumping引理并不适用于所有的Petri网语言.文中给出了一种Petri网语言的Pumping引理,证明其对任意无空标注的Petri网语言都有效,并且正规语言的Pumping引理是此引理的一种特殊形式.利用此Pumping引理可以证明某些语言是不能由Petri网产生的.

Pumping引理的Petri网描述──Petri网语言属型的一组判定条件

本文通过Ｐｕｍｐｉｎｇ引理在Ｐｅｔｒｉ网的变迁节引发序列中的反映，揭示了对应的Ｐｅｔｒｉ网结构内涵，从而给出了判定一个标准Ｐｅｔｒｉ网产生的语言分别为正规语言或上下文无关语言的充要条件．这样，就可以从网的结构直接判断其语言属型．

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

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

稠密相对正则语言的一些性质

主要讨论了稠密相对正则语言的一些性质.相对于正则语言的pumping引理,给出了稠密相对正则语言的类似结论.继而证明了稠密相对正则语言都含有本原字.最后给出了稠密相对正则语言和极大码的一些联系.

可交换上下文无关文法

本文提出了可交换上下文无关文法及其该文法产生的语言——可交换上下文无关语言,证明了正规语言类是可交换上下文无关语言类的一个子集,而可交换上下文无关语言类是上下文无关语言类的一个子集;讨论了可交换上下文无关语言的结构特点,并给出了可交换上下文无关语言的Pumping引理。

上下文无关语言的可重复序列及其性质

通过分析下推自动机的运行规律和特点,提出上下文无关语言的可重复序列的概念,将其划分为平衡重复序列、增重复序列、减重复序列三类;研究了这三类可重复序列在下推自动机的状态转换图中的结构表现和性质,通过分析下推自动机状态转换图中标注回路与可重复序列之间的关系,给出求解可重复序列的计算方法;证明了不同类型的可重复序列对上下文无关语言性质的影响,利用可重复序列揭示了上下文无关语言的Pumping引理的本质特征,并给出正规语言判定的一个充分必要条件.