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

An approach to distinguishing the levels of free-labeled L-type Petri net languages in the Chomsky hierarchy

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

Petri nets （PNs） and automatic machines are two approaches to modeling discrete event dynamic systems. The relationship between these approaches is important for controlling discrete event dynamic systems. This paper investigates the relationship between these approaches from the formal language point of view, i.e., we introduce an approach to distinguishing the levels of free-labeled L-type PN languages in the Chomsky hierarchy. To characterize PNs from the formal language point of view, the concepts of increaser, valid increaser, and linearer are introduced. For a PN with no valid increaser, its PN language is regular. For a PN with a valid increaser with at least two linearers, its PN language is context-sensitive. For a PN in which each valid increaser has only one linearer, assuming only one increaser in the PN, the PN language is context-free. If the PN has more than one increaser, the corresponding PN language is context-sensitive when valid increasers and their linearers can be fired currently or crossed. The language is context-free when the increasers and their linearers are fired alternatively, or an increaser and its linearer are fired sequentially relative to other increasers and their linearers, or when firing occurs after an increaser and before its linearer.