无标注L型Petri网语言属性判定的一种方法

摘要

Petri网和自动机是离散事件动态系统建模的两种重要方法,研究这两种模型之间的关系,对于更好地理解和控制离散事件动态系统的行为具有重要作用.本文从形式语言的角度对该问题进行了研究,提出了判定无标注L型Petri网语言属性的方法,引入有效递增子和线性子等概念来刻画Petri网语言的性质.对于一个Petri网PN,当PN没有有效递增子时,PN对应的Petri网语言是正则语言.当PN的某个有效递增子有两个及其以上线性子时,PN对应的Petri网语言是上下文有关的.当PN的所有有效递增子只有一个线性子时,如果只有一个有效递增子,则PN对应的Petri网语言是上下文无关的;如果PN有两个及其以上有效递增子,则顺序引发、嵌套引发和选择引发时PN对应的Petri网语言是上下文无关的,并发引发和交叉引发时PN对应的Petri网语言是上下文相关的.本文还对可达树进行了改进,给出了利用改进后的可达树来判定有效递增子的方法,从而使得本文给出的判定无标注L型Petri网语言属性的方法具有可操作性.