Place-labelled Petri net controlled grammars

Nurhidaya Mohamad Jan, Sherzod Turaev, Wan Heng Fong, Nor Haniza Sarmin

Research output: Contribution to journalArticlepeer-review


A place-labelled Petri net (pPN) controlled grammar is a context-free grammar equipped with a Petri net and a function which maps places of the net to the productions of the grammar. The language consists of all terminal strings that can be obtained by simultaneously applying the rules of multisets which are the images of the sets of the input places of transitions in a successful occurrence sequence of the Petri net. In this paper, we study the generative power and structural properties of pPN-controlled grammars. We show that pPN-controlled grammars have the same generative power as matrix grammars. Moreover, we prove that for each pPN-controlled grammar, we can construct an equivalent place-labelled ordinary net controlled grammar.

Original languageEnglish
Pages (from-to)9-19
Number of pages11
Publication statusPublished - Feb 2017
Externally publishedYes


  • Computational power
  • Context-free grammars
  • Structural properties

ASJC Scopus subject areas

  • General


Dive into the research topics of 'Place-labelled Petri net controlled grammars'. Together they form a unique fingerprint.

Cite this