Petri网语言的Pumping引理

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

可交换上下文无关文法

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

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

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

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

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

正规语言闭包运算的Petri网构造方法

Petri网语言与Chomsky文法体系之间的关系已有了一些结论,已经证明正规语言是Petri网语言的一个子类。相关文献中给出了一种Petri网子类——恰当终结的标准Petri网,并且已经证明恰当终结的标准Petri网语言与正规语言的等价性。在此基础上,研究了正规表达式中Kleene闭包运算“*”的Petri网构造方法,分别给出了Kleene闭包运算“*”的ε-空标注和无ε-空标注Petri网模型的构造方法。该构造方法可由产生正规语言L的网模型直接得到产生正规语言L*的网模型。证明了对于恰当终结的标准Petri网,正规语言闭包运算“*”的构造是封闭的。     

正规表达式与恰当终结的标准Petri网

给出了一种较特殊的Petri网子类——恰当终结的标准Petri网，可以证明恰当终结的标准Petri网产生的语言是正规语言，反之任一正规语言都可由恰当终结的标准Petri网产生。研究了恰当终结的标准Petri网语言关于连接运算“ ”、选择(并)运算“∪”、kleene闭包运算“*”、并行运算“//”的性质，给出了用恰当终结的标准Petri网(带空标注)模拟和带并发算子的正规表达式的方法。     

Petri网语言与传统形式语言的关系

本文介绍了一种形式语言－Ｐｅｔｒｉ网语言，并讨论了Ｐｅｔｒｉ网语言与传统形式语言（正规语言，上下文无关语言，上下文有关语言以及递归枚举语言）的关系。     

推导可交换上下文无关语言

提出了推导可交换上下文无关语言及其文法,证明了正规语言类和有界上下文无关语言类都是推导可交换上下文无关语言类的子集,而推导可交换上下文无关语言类是上下文无关语言类的一个子集;定义了该类语言的α闭包等有关运算,给出了推导可交换上下文无关语言表达式,证明了推导可交换上下文无关文法、推导可交换上下文无关语言表达式之间的等价转换.     

Petri网语言表达式及其求解算法

Petri网语言是描述网系统动作序列的集合.为了给出一个网系统语言的形式描述,基于Petri网的状态转换图,分析了Petri网的行为特征,定义了α闭包表达式和Petri网语言表达式,给出了求解Petri网语言表达式的算法,为Petri网语言的形式化描述和分析提供了一种新方法.     

ω上下文无关语言和语言的附着之间的关系

文章研究了用重复集生成的ω语言和语言的附着之间的关系,指出并证明了上下文无关语言附着类是ω上下文无关语言类的真子类,正规语言附着类是ω正规语言类的真子类．作为上下文无关语言的一个真子类——线性语言的附着类是ω正规语言类的真子类.     

Pumping lemmas for term languages

Pumping lemmas are stated and proved for the classes of regular and context-free sets of terms. The lemmas are then applied to solve decision problems concerning these classes of sets.     

Petri net algorithms in the theory of matrix grammars

This paper shows that the languages over a one-letter alphabet generated by context-free matrix grammars are always regular. Moreover we give a decision procedure for the question of whether a context-free matrix language is finite. Hereby we strengthen a result of [Mk 92] and settle a number of open questions in [DP 89]. Both results are obtained by a reduction to Petri net problems.     

Parikh?s theorem: A simple and direct automaton construction

Parikh?s theorem states that the Parikh image of a context-free language is semilinear or, equivalently, that every context-free language has the same Parikh image as some regular language. We present a very simple construction that, given a context-free grammar, produces a finite automaton recognizing such a regular language.     

有界Petri网的最小化化简

给出了Petri网的语言等价性概念和有界Petri网的最小化概念；证明了有限状态自动机、有界Petri网、正规文法的等价性，给出了它们之间等价转换的算法；分析了有界Petri网的化简过程，并给出了有界Petri网最小化化简的算法，为有界Petri网的自动化化简提供了方法。