SCIENTIA SINICA Informationis, Volume 47, Issue 6: 696(2017) https://doi.org/10.1360/N112016-00056

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

More info
  • ReceivedNov 9, 2016
  • AcceptedDec 21, 2016
  • PublishedMar 6, 2017


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.

Funded by





Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1       京公网安备11010102003388号