Open access peer-reviewed chapter

Grammars Controlled by Petri Nets

By J. Dassow, G. Mavlankulov, M. Othman, S. Turaev, M.H. Selamat and R. Stiebe

Submitted: December 20th 2011Reviewed: June 12th 2012Published: August 29th 2012

DOI: 10.5772/50637

Downloaded: 1552

1. Introduction

Formal language theory, introduced by Noam Chomsky in the 1950s as a tool for a description of natural languages [8, 9, 10], has also been widely involved in modeling and investigating phenomena appearing in computer science, artificial intelligence and other related fields because the symbolic representation of a modeled system in the form of strings makes its processes by information processing tools very easy: coding theory, cryptography, computation theory, computational linguistics, natural computing, and many other fields directly use sets of strings for the description and analysis of modeled systems. In formal language theory a model for a phenomenon is usually constructed by representing it as a set of words, i.e., a language over a certain alphabet, and defining a generative mechanism, i.e., a grammar which identifies exactly the words of this set. With respect to the forms of their rules, grammars and their languages are divided into four classes of Chomsky hierarchy: recursively enumerable, context-sensitive, context-free and regular.

Context-free grammars are the most investigated type of Chomsky hierarchy which, in addition, have good mathematical properties and are extensively used in many applications of formal languages. However, they cannot cover all aspects which occur in modeling of phenomena. On the other hand, context-sensitive grammars, the next level in Chomsky hierarchy, are too powerful to be used in applications of formal languages, and have bad features, for instance, for context-sensitive grammars, the emptiness problem is undecidable and the existing algorithms for the membership problem, thus for the parsing, have exponential complexities. Moreover, such concepts as a derivation tree, which is an important tool for the analysis of context-free languages, cannot be transformed to context-sensitive grammars. Therefore, it is of interest to consider “intermediate” grammars which are more powerful than context-free grammars and have similar properties. One type of such grammars, called grammars with regulated rewriting (controlled or regulated grammars for short), is defined by considering grammars with some additional mechanisms which extract some subset of the generated language in order to cover some aspects of modeled phenomena. Due to the variety of investigated practical and theoretical problems, different additional mechanisms to grammars can be considered. Since Abraham [1] first defined matrix grammars in 1965, several grammars with restrictions such as programmed, random context, valence grammars, and etc., have been introduced (see [16]). However, the rapid developments in present day technology, industry, medicine and other areas challenge to deal with more and more new and complex problems, and to look for new suitable tools for the modeling and investigation of these problems. Petri net controlled grammars, which introduce concurrently parallel control mechanisms in formal language theory, were proposed as a theoretical model for some problems appearing in systems biology and automated manufacturing systems (see [18, 19, 20, 21, 22, 23, 56, 59, 60, 61, 62]).

Petri nets, which are graphical and mathematical modeling tools applicable to many concurrent, asynchronous, distributed, parallel, nondeterministic and stochastic systems, have widely been used in the study of formal languages. One of the fundamental approaches in this area is to consider Petri nets as language generators. If the transitions in a Petri net are labeled with a set of (not necessary distinct) symbols, a sequence of transition firing generates a string of symbols. The set of strings generated by all possible firing sequences defines a language called a Petri net language, which can be used to model the flow of information and control of actions in a system. With different kinds of labeling functions and different kinds of final marking sets, various classes of Petri net languages were introduced and investigated by Hack [34] and Peterson [46]. The relationship between Petri net languages and formal languages were thoroughly investigated by Peterson in [47]. It was shown that all regular languages are Petri net languages and the family of Petri net languages are strictly included in the family of context-sensitive languages but some Petri net languages are not context-free and some context-free languages are not Petri net languages. It was also shown that the complement of a free Petri net language is context-free [12].

Another approach to the investigation of formal languages was considered by Crespi-Reghizzi and Mandrioli [11]. They noticed the similarity between the firing of a transition and application of a production rule in a derivation in which places are nonterminals and tokens are separate instances of the nonterminals. The major difference of this approach is the lack of ordering information in the Petri net contained in the sentential form of the derivation. To accommodate it, they defined the commutative grammars, which are isomorphic to Petri nets. In addition, they considered the relationship of Petri nets to matrix, scattered-context, nonterminal-bounded, derivation-bounded, equal-matrix and Szilard languages in [13].

The approach proposed by Crespi-Reghizzi and Mandrioli was used in the following works. By extending the type of Petri nets introduced in [11] with the places for the terminal symbols and arcs for the control of nonterminal occurrences in sentential forms, Marek and C˘eška showed that for every random-context grammar, an isomorphic Petri net can be constructed, where each derivation of the grammar is simulated by some occurrence sequence of transitions of the Petri net, and vice versa. In [39] the relationship between vector grammars and Petri nets was investigated, partially, hybrid Petri nets were introduced and the equality of the family of hybrid Petri net languages and the family of vector languages was shown. By reduction to Petri net reachability problems, Hauschildt and Jantzen [35] could solve a number of open problems in regulated rewriting systems, specifically, every matrix language without appearance checking over one letter alphabet is regular and the finiteness problem for the families of matrix and random context languages is decidable; In several papers [2, 14, 25], Petri nets are used as minimization techniques for context-free (graph) grammars. For instance, in [2], algorithms to eliminate erasing and unit (chain) rules, algorithms to remove useless rules using the Petri net concept are introduced.

Control by Petri nets has also been introduced and studied in automata theory [26, 27, 28, 38] and grammar systems theory [6].

In this chapter we summarize the recent obtained results on Petri net controlled grammars and propose new problems for further research.

In Section 2 we recall some basic concepts and results from the areas formal languages and Petri nets: strings, grammars, languages, Petri nets, Petri net languages and so on, which will be used in the next sections.

In Section 3 we define a context-free Petri net (a cf Petri net for short), where places correspond to nonterminals, transitions are the counterpart of the production rules, the tokens reflect the occurrences of symbols in the sentential form, and there is a one-to-one correspondence between the application of (sequence of) rules and the firing of (sequence of) transitions. Further, we introduce grammars controlled by k-Petri nets, i.e., cf Petri nets with additional kplaces, and studies the computational power and closure properties of families of languages generated by k-Petri net controlled grammars.

In Section 4 we consider a generalization of the k-Petri net controlled grammars: we associate an arbitrary place/ transition net with a context-free grammar and require that the sequence of applied rules corresponds to an occurrence sequence of transitions in the Petri net. With respect to different labeling strategies and different definitions of final marking sets, we define various classes of Petri net controlled grammars. Here we study the influence of the labeling functions and the effect of the final markings on the generative power.

It is known that many decision problems in formal language theory are equivalent to the reachability problem in Petri net theory, which has been shown that it is decidable, however, it has exponential time complexity. The result of this has been the definition of a number of structural subclasses of Petri nets with a smaller complexity and still adequate modeling power. Thus, it is interesting to consider grammars controlled by such kind of subclasses of Petri nets. In Section 5 we continue our study of arbitrary Petri net controlled grammars by restricting Petri nets to their structural subclasses, i.e., special Petri nets such as state machines, marked graphs, and free-choice nets, and so on.

In Section 6 we examine Petri net controlled grammars with respect to dynamical properties of Petri nets: we use (cf and arbitrary) Petri nets with place capacities. We also investigate capacity-bounded grammars which are counterparts of grammars controlled by Petri nets with place capacities.

In Section 7 we draw some general conclusions and present suggestions for further research.

2. Preliminaries

In this section we recall some prerequisites, by giving basic notions and notations of the theories formal languages, Petri nets and Petri net languages which are used in the next sections. The reader is referred to [16, 34, 36, 42, 45, 47, 50, 52] for further information.

2.1. General notions and notations

Throughout the chapter we use the following general notations. denotes the membership of an element to a set while the negation of set membership is denoted by. The inclusion is denoted by and the strict (proper) inclusion is denoted by. The symbol denotes the empty set. The set of positive (non-negative) integers is denoted by N(N0). The set of integers is denoted byZ. The power set of a set Xis denoted by2X, while the cardinality of a set Xis denoted by|X|.

Let Σbe an alphabet which is a finite nonempty set of symbols. A string (sometimes a word) over the alphabet Σis a finite sequence of symbols fromΣ. The empty string is denoted byλ. The length of a wordw, denoted by|w|, is the number of occurrences of symbols inw. The number of occurrences of a symbol ain a string wis denoted by|w|a. The set of all strings over the alphabet Σis denoted byΣ*. The set of nonempty strings over Σis denoted byΣ+, i.e.,Σ+=Σ*-{λ}. A subset of Σ*is called a language. A language LΣ*is λ-free ifλL. For two languages L1,L2Σ*the operation shuffle is defined by

Shuf(L1,L2)={u1v1u2v2unvn|u1u2unL1,v1v2vnL2,E1
ui,viΣ*,1in}E2

and forLΣ*, Shuf*(L)=k1Shufk(L)where

Shuf1(L)=L and Shufk(L)=Shuf(Shufk-1(L),L),k2.E3

2.2. Grammars

A phrase structure (Chomsky) grammar is a quadruple G=(V,Σ,S,R)where Vand Σare two disjoint alphabets of nonterminal and terminal symbols, respectively, SVis the start symbol and R(VΣ)*V(VΣ)*×(VΣ)*is a finite set of (production) rules. Usually, a rule (u,v)Ris written in the formuv. A rule of the form uλis called an erasing rule.

A phrase structure grammar G=(V,Σ,S,R)is called a GS grammar (a phrase structure grammar due to Ginsburg and Spanier [31]) if RV+×(VΣ)*.

The families of languages generated by GS grammars and by phrase structure grammars are denoted by GSandRE, respectively. It is well-known that the family GSis equal to the familyRE.

A string x(VΣ)*directly derives a string y(VΣ)*inG, written as xyif and only if there is a rule uvRsuch that x=x1ux2and y=x1vx2for somex1,x2(VΣ)*. The reflexive and transitive closure of the relation is denoted by*. A derivation using the sequence of rulesπ=r1r2rk, riR, 1ik, is denoted by πorr1r2rk. The language generated byG, denoted byL(G), is defined by L(G)={wΣ*|S*w}.

A phrase-structure grammar G=(V,Σ,S,R)is called context-sensitive if each rule uvRhasu=u1Au2, v=u1xu2foru1,u2(VΣ)*, AVand x(VΣ)+(in context sensitive grammars Sλis allowed, provided that Sdoes not appear in the right-hand members of rules inR); context-free if each rule uvRhasuV; linear if each rule uvRhas uVandvΣ*Σ*VΣ*; regular if each rule uvRhas uVandvΣΣV.

The families of languages generated by context-sensitive, context-free, linear and regular grammars are denoted byCS, CF, LINandREG, respectively. Further we denote the family of finite languages byFIN. The next strict inclusions, named Chomsky hierarchy, hold (for details, see [52]):

Theorem 1 FINREGLINCFCSRE.

2.3. Regulated grammars

The idea of regulated rewriting consists of restricting the application of the rules in a context-free grammar in order to avoid some derivations and hence obtaining a subset of the context-free language generated in usual way. The computational power of some context-free grammars with regulated rewriting turns out to be greater than the power of context-free grammars.

A regularly controlled grammar is a quintuple G=(V,Σ,S,R,K)where V,Σ,S,Rare specified as in a context-free grammar and Kis a regular set overR. The language generated by Gconsists of all words wΣ*such that there is a derivation Sr1r2rnwwherer1r2rnK.

A matrix grammar is a quadruple G=(V,Σ,S,M)where V,Σ,Sare defined as for a context-free grammar, Mis a finite set of matrices which are finite strings over a set Rof context-free rules (or finite sequences of context-free rules). The language generated by the grammar Gis L(G)={wΣ*|SπwandπM*}.

A vector grammar is a quadruple G=(V,Σ,S,M)whose components are defined as for a matrix grammar. The language generated by the grammar Gis defined by

L(G)={wΣ*|SπwandπShuf*(M)}.E4

An additive valence grammar is a quintuple G=(V,Σ,S,R,v)whereV, Σ, S, Rare defined as for a context-free grammar and vis a mapping from RintoZ. The language generated by Gconsists of all strings wΣ*such that there is a derivation Sr1r2rnwwhere i=1nv(ri)=0.

A positive valence grammar is a quintuple G=(V,Σ,S,R,v)whose components are defined as for additive valence grammars. The language generated by Gconsists of all strings wΣ*such that there is a derivation Sr1r2rnwwhere i=1nv(ri)=0and for any1j<n,i=1jv(ri)0.

The families of languages generated by regularly controlled, matrix, vector, additive valence and positive valence grammars (with erasing rules) are denoted byrC, MAT, VEC, aV, pV(rCλ, MATλ, VECλ, aVλ,pVλ), respectively.

Theorem 2 The following inclusions and equalities hold (for details, see [16]):

  1. CFaV=aVλMAT=rC=pV;E5
  2. MATVECCS;E6
  3. MATMATλ=rCλ=VECλ=pVλRE.E7

2.4. Petri nets

A Petri net (PN) is a construct N=(P,T,F,ϕ)where Pand Tare disjoint finite sets of places and transitions, respectively, F(P×T)(T×P)is the set of directed arcs, ϕ:FNis a weight function.

A Petri net can be represented by a bipartite directed graph with the node set PTwhere places are drawn as circles, transitions as boxes and arcs as arrows. The arrow representing an arc (x,y)Fis labeled withϕ(x,y); ifϕ(x,y)=1, then the label is omitted.

An ordinary net (ON) is a Petri net N=(P,T,F,ϕ)where ϕ(x,y)=1for all(x,y)F. We omit ϕfrom the definition of an ordinary net, i.e.,N=(P,T,F).

A mapping μ:PN0is called a marking. For each placepP, μ(p)gives the number of tokens inp. Graphically, tokens are drawn as small solid dots inside circles.  x={y| (y,x)F}and x={y| (x,y)F}are called pre- and post-sets ofxPT, respectively. For tT(pP), the elements of  t (p)are called input places (transitions) and the elements of t (p)are called output places (transitions) oft (p).

A transition tTis enabled by marking μif and only if μ(p)ϕ(p,t)for allp t. In this case tcan occur (fire). Its occurrence transforms the marking μinto the marking μ'defined for each place pPbyμ'(p)=μ(p)-ϕ(p,t)+ϕ(t,p). We writeμtμ'to indicate that the firing of tin μleads toμ'. A marking μis called terminal if in which no transition is enabled. A finite sequencet1t2tk, tiT,1ik, is called an occurrence sequence enabled at a marking μand finished at a marking μkif there are markings μ1,μ2,,μk-1such thatμt1μ1t2tk-1μk-1tkμk. In short this sequence can be written as μt1t2tkμkor μνμkwhereν=t1t2tk. For each1ik, marking μiis called reachable from markingμ. R(N,μ)denotes the set of all reachable markings from a markingμ.

A marked Petri net is a system N=(P,T,F,ϕ,ι)where (P,T,F,ϕ)is a Petri net, ιis the initial marking.

A Petri net with final markings is a construct N=(P,T,F,ϕ,ι,M)where (P,T,F,ϕ,ι)is a marked Petri net and MR(N,ι)is set of markings which are called final markings. An occurrence sequence νof transitions is called successful for Mif it is enabled at the initial marking ιand finished at a final marking τofM. If Mis understood from the context, we say that νis a successful occurrence sequence.

A Petri net Nis said to be k-bounded if the number of tokens in each place does not exceed a finite number kfor any marking reachable from the initial markingι, i.e., μ(p)kfor all pPand for allμR(N,ι). A Petri net Nis said to be bounded if it is k-bounded for somek1.

A Petri net with place capacity is a system N=(P,T,F,ϕ,ι,κ)where (P,T,F,ϕ,ι)is a marked Petri net and κ:PN0is a function assigning to each place a number of maximal admissible tokens. A marking μof the net Nis valid ifμ(p)κ(p), for each placepP. A transition tTis enabled by a marking μif additionally the successor marking is valid.

2.5. Special Petri nets

It is known that many decision problems are equivalent to the reachability problem [33], which has been shown to be decidable. However, it has exponential space complexity [40], thus from a practical point of view, Petri nets may be too powerful to be analyzed. The result of this has been the definition of a number of subclasses of Petri nets in order to find a subclass with a smaller complexity and still adequate modeling power for practical purposes. These subclasses are defined by restrictions on their structure intended to improve their analyzability. We consider the following main structural subclasses of Petri nets.

A state machine (SM) is an ordinary Petri net such that each transition has exactly one input place and exactly one output place, i.e., |t|=|t|=1for alltT. This means that there can not be concurrency but there can be conflict.

A generalized state machine (GSM) is an ordinary Petri net such that |t|1and |t|1for alltT.

A marked graph (MG) is an ordinary Petri net such that each place has exactly one input transition and exactly one output transition, i.e., |p|=|p|=1for allpP. This means that there can not be conflict but there can be concurrency.

A generalized marked graph (GMG) is an ordinary Petri net such that |p|1and |p|1for allpP.

A casual net (CN) is a generalized marked graph each subgraph of which is not a a cycle.

A free-choice net (FC) is an ordinary Petri net such every arc is either the only arc going from the place, or it is the only arc going to a transition, i.e., that if p1p2then |p1|=|p2|=1for allp1,p2P. This means that there can be both concurrency and conflict but not the same time.

An extended free-choice net (EFC) is an ordinary Petri net such that if p1p2then p1=p2for allp1,p2P.

An asymmetric choice net (AC) is an ordinary Petri net such that if p1p2then p1p2or p1p2for allp1,p2P. In asymmetric choice nets concurrency and conflict (in sum, confusion) may occur but not asymmetrically.

3. k -Petri net controlled grammars

Since a context-free grammar and its derivation process can also be described by a Petri net (see [11]), where places correspond to nonterminals, transitions are the counterpart of the production rules, and the tokens reflect the occurrences of symbols in the sentential form, and there is a one-to-one correspondence between the application of (sequence of) rules and the firing of (sequence of) transitions, it is a very natural and very easy idea to control the derivations in a context-free grammar by adding some features to the associated Petri net. In this section we introduce a Petri net associated with a context-free grammar (i.e., a context-free Petri net), construct Petri net control mechanisms from cf Petri nets by adding new places, and define the corresponding grammars, called k-Petri net controlled grammars.

The construction of the following type of Petri nets is based on the idea of using similarity between the firing of a transition and the application of a production rule in a derivation in which places are nonterminals and tokens are separate occurrences of nonterminals.

Definition 1 A context-free Petri net (in short, a cf Petri net) w.r.t. a context-free grammar kis a septuple G=(V,Σ,S,R)where

  • N=(P,T,F,ϕ,β,γ,ι)
  • labeling functions (P,T,F,ϕ)and β:PVare bijections;

  • there is an arc from place γ:TRto transition pif and only if tandγ(t)=Aα. The weight of the arc β(p)=Ais 1;

  • there is an arc from transition (p,t)to place tif and only if pand γ(t)=Aαwhereβ(p)=x. The weight of the arc |α|x>0is(t,p);

  • the initial marking |α|xis defined by ιand ι(β-1(S))=1for allι(p)=0.

Example 1 Let pP-{β-1(S)}be a context-free grammar with the rules:

G1E8

(the other components of the grammar can be seen from these rules). Figure 1 illustrates a cf Petri net r0:SAB, r1:AaAb, r2:Aab, r3:BcB, r4:Bcwith respect to the grammarN1. Obviously, G1

Figure 1.

A cf Petri net L(G1)={anbncm|n,m≥1}.

The following proposition shows the similarity between terminal derivations in a context-free grammar and successful occurrences of transitions in the corresponding cf Petri net.

Proposition 3 Let N1be the cf Petri net with respect to a context-free grammarN=(P,T,F,ϕ,ι,β,γ). ThenG=(V,Σ,S,R), Sr1r2⋯rn  wis a derivation in w∈Σ*iffG, t1t2⋯tn, is an occurrence sequence of transitions in ι→t1t2⋯tn  μnsuch that Nand γ(t1t2⋯tn)=r1r2⋯rn for allμn(p)=0.

Now we define a pP-Petri net, i.e., a cf Petri net with additional kplaces and additional arcs from/to these places to/from transitions of the net, the pre-sets and post-sets of the additional places are disjoint.

Definition 2 Let kbe a context-free grammar with its corresponding cf Petri netG=(V,Σ,S,R). Let N=(P,T,F,ϕ,β,γ,ι)be a positive integer and let kbe a set of new places called counters. A Q={q1,q2,,qk}-Petri net is a construct kwhere

  • Nk=(PQ,T,FE,φ,ζ,γ,μ0,τ)E={(t,qi)|tT1i, 1ik}{(qi,t)|tT2i,1ik}T1iTT2iT1ikTliTlj=1l2T1iT2j=1i<jkT1i=T2i=
  • the weight function 1ikis defined by φ(x,y)if φ(x,y)=ϕ(x,y)and (x,y)Fifφ(x,y)=1,

  • the labeling function (x,y)Eis defined by ζ:PQV{λ}if ζ(p)=β(p)and pPifζ(p)=λ,

  • the initial marking pQis defined by μ0and μ0(β-1(S))=1for allμ0(p)=0,

  • pPQ-{β-1(S)}ττ(p)=0

Definition 3 A p∈P∪Q-Petri net controlled grammar (k-PN controlled grammar for short) is a quintuple kwhere G=(V,Σ,S,R,Nk)are defined as for a context-free grammar and V,Σ,S,Ris a Nk-PN with respect to the context-free grammark.

Definition 4 The language generated by a (V,Σ,S,R)-Petri net controlled grammar kconsists of all strings Gsuch that there is a derivation

wΣ*E9

is an occurrence sequence of the transitions of Sr1r2rn  wwheret1t2tn=γ-1(r1r2rn)T*enabled at the initial marking Nkand finished at the final markingι.

We denote the family of languages generated by τ-PN controlled grammars (with erasing rules) by k(PNk),PNkλ.

Example 2 Let k1be a 2-PN controlled grammar with the production rules:

G2E10

and the corresponding 2-Petri net r0:SA1B1A2B2,    r1:A1a1A1b1,    r2:A1a1b1,r3:B1c1B1,    r4:B1c1,    r5:A2a2A2b2,r6:A2a2b2,    r7:B2c2B2,    r8:B2c2is given in Figure 2. Then it is easy to see that N2generates the language

G2E11

Figure 2.

A 2-Petri net L(G2)={a1nb1nc1na2mb2mc2m|n,m≥1}.

Theorem 4 The language

N2E12

where L=i=1k+1ainibiniciniandk1, cannot be generated by a ni1, 1ik+1-PN controlled grammar.

The following theorem presents the relations of languages generated by k-Petri net controlled grammars to context-free, (positive) additive valence and vector languages.

Theorem 5

kE13

The next theorem shows that the language families generated by CFPN1[λ]pV[λ],  aV[λ]PN2[λ] and PNn[λ]VEC[λ],n1.-Petri net controlled grammars form infinite hierarchy with respect to the numbers of additional places.

Theorem 6 Fork, k1

The closure properties of the language families generated by PNk[λ]PNk+1[λ].-PN controlled grammars are given in the following theorem.

Theorem 7 The family of languagesk, PNk, is closed under union, substitution, mirror image, intersection with regular languages and it is not closed under concatenation.

4. Arbitrary Petri net controlled grammars

In this section we consider a generalization of regularly controlled grammars: instead of a finite automaton we associate a Petri net with a context-free grammar and require that the sequence of applied rules corresponds to an occurrence sequence of the Petri net, i.e., to sequences of transitions which can be fired in succession. However, one has to decide what type of correspondence is used and what concept is taken as an equivalent of acceptance. Since the sets of occurrence sequences form the language of a Petri net, we choose the correspondence and the equivalent for acceptance according to the variations which are used in the theory of Petri net languages.

Therefore as correspondence we choose a bijection (between transitions and rules) or a coding (any transition is mapped to a rule) or a weak coding (any transition is mapped to a rule or the empty word) which agree with the classical three variants of Petri net languages (see e.g. [34, 57, 58]).

We consider two types of acceptance from the theory of Petri net languages: only those occurrence sequences belonging to the languages which transform the initial marking into a marking from a given finite set of markings or all occurrence sequences are taken (independent of the obtained marking). If we use only the occurrence sequence leading to a marking in a given finite set of markings we say that the Petri net controlled grammar is of k1-type; if we consider all occurrence sequences, then the grammar is of t-type. We add a further type which can be considered as a complement of the r-type. Obviously, if we choose a finite set tof markings and require that the marking obtained after the application of the occurrence sequence is smaller than at least one marking of M(the order is componentwise), then we can choose another finite set Mof markings and require that the obtained marking belongs toM'. The complementary approach requires that the obtained marking is larger than at least one marking of the given setM'. The corresponding class of Petri net controlled grammars is called of M-type. Therefore, we obtain nine classes of Petri net controlled grammars since we have three different types of correspondence and three types of the set of admitted occurrence sequences. These types of control are generalizations of those types of control considered in the previous chapter, too, where instead of arbitrary Petri nets only such Petri nets have been considered where the places and transitions correspond in a one-to-one manner to nonterminals and rules, respectively.

We now introduce the concept of control by an arbitrary Petri net.

Definition 5 An arbitrary Petri net controlled grammar is a tuple gwhere G=(V,Σ,S,R,N,γ,M)are defined as for a context-free grammar and V,Σ,S,Ris a (marked) Petri net, N=(P,T,F,φ,ι)is a transition labeling function and γ:TR{λ}is a set of final markings.

Definition 6 The language generated by a Petri net controlled grammarM, denoted byG, consists of all strings L(G)such that there is a derivation wΣ*and an occurrence sequence Sr1r2rk  wΣ*which is successful for ν=t1t2tssuch thatM.

Example 3 Let r1r2rk=γ(t1t2ts)be a Petri net controlled grammar where G3=({S,A,B,C},{a,b,c},S,R,N3,γ,M)consists of

RE14

and SABC,        AaA,    BbB,    CcC,Aa,    Bb,    Ccis illustrated in Figure 3. If N3is the set of all reachable markings, then Mgenerates the language

G3E15

If L(G3)={anbmck|nmk1}.with M={μ}for allμ(p)=0, then it generates the language

pPE16

Figure 3.

A labeled Petri net L(G3)={anbncn|n≥1}.

Different labeling strategies and different definitions of the set of final markings result in various types of Petri net controlled grammars. We consider the following types of Petri net controlled grammars.

Definition 7 A Petri net controlled grammar N3is called free (abbreviated byG=(V,Σ,S,R,N,γ,M)) if a different label is associated to each transition, and no transition is labeled with the empty string; f-free (abbreviated byλ) if no transition is labeled with the empty string; extended (abbreviated by-λ) if no restriction is posed on the labeling functionλ.

Definition 8 A Petri net controlled grammar γis called r-type if G=(V,Σ,S,R,N,γ,M)is the set of all reachable markings from the initial markingM, i.e.,ι; t-type if M=R(N,ι)is a finite set; g-type if for a given finite setMR(N,ι), M0R(N,ι)is the set of all markings such that for every marking Mthere is a marking μMsuch thatμ'M0.

We use the notation μμ'-PN controlled grammar where (x,y)shows the type of a labeling function and x{f,-λ,λ}shows the type of a set of final markings. We denote by y{r,t,g}and PN(x,y)the families of languages generated by PNλ(x,y)-PN controlled grammars without and with erasing rules, respectively, where (x,y)andx{f,-λ,λ}.

The following theorem shows that the labeling strategy does not effect on the generative capacity of arbitrary Petri net controlled grammars.

Theorem 8 Fory{r,t,g},

y{r,t,g}E17

Not surprisingly, arbitrary Petri net controlled grammars generate matrix languages. Moreover, in [65] it was proven that the erasing rules in arbitrary Petri net controlled grammars can be eliminated without effecting on the generative power of the grammars. If we take into consideration this result, we obtain the following inclusions and equalities:

Theorem 9 For PN[λ](f,y)=PN[λ](-λ,y)=PN[λ](λ,y).andx{f,-λ,λ},

y{r,t,g}E18

5. Grammars controlled by special Petri nets

In the previous section we investigated arbitrary Petri net controlled grammars in dependence on the type of labeling functions and on the definitions of final markings, and showed that Petri net controlled grammars have the same power as some other regulating mechanisms such as matrices, finite automata. If we consider these matrices and finite automata in terms of control mechanisms, special types of matrices and special regular languages are widely investigated in literature, for instance, as control, simple matrices ([37]) or some subclasses of regular languages ([15, 17]) are considered. Thus, it is also natural to investigate grammars controlled by some special classes of Petri nets. We consider (generalized) state machines, (generalized) marked graphs, causal nets, (extended) free-choice nets, asymmetric choice nets and ordinary nets. Similarly to the general case we also investigate the effects of labeling policies and final markings to the computational power, and prove that the family of languages generated by (arbitrary) Petri net controlled grammars coincide with the family of languages generated by grammars controlled by free-choice nets.

Let MATPN(x,r)=PN(x,g)PN(x,t)=PNλ(x,y)=MATλ.be an arbitrary Petri net controlled grammar. The grammar G=(V,Σ,S,R,N,γ,M)is called a (generalized) state machine, (generalized) marked graph, causal net, (extended) free-choice net, asymmetric choice net or ordinary net controlled grammar if the net Gis a (generalized) state machine, (generalized) marked graph, causal net, (extended) free-choice net, asymmetric choice net or ordinary net, respectively.

We also use a notation an N-(generalized) state machine, ((generalized) marked graph, causal net, (extended) free-choice net, asymmetric choice net and ordinary net) controlled grammar where (x,y)shows the type of a labeling function x{f,-λ,λ}and γshows the type of a set of final markings.

We denote the families of languages generated by grammars controlled by state machines, generalized state machines, marked graphs, generalize marked graphs, causal nets, free-choice nets, extended free-choice nets, asymmetric nets, ordinary nets and Petri nets

y{r,t,g}E19

where SM[λ](x,y),GSM[λ](x,y),MG[λ](x,y),GMG[λ](x,y),CN[λ](x,y),FC[λ](x,y),EFC[λ](x,y),AC[λ](x,y),ON[λ](x,y),PN[λ](x,y)andx{f,-λ,λ}.

The inclusion y{r,t,g}immediately follows from the definition where

  • X(x,y)Xλ(x,y)E20
  • X{SM,GSM,MG,GMG,CN,FC,EFC,AC,ON}
    x{f,-λ,λ}E21

Example 4 Let y{r,t,g}be a SM controlled grammar where G4=({S,A,B},{a,b},S,R,N4,γ,M)consists of

RE22

the Petri net SAB,        AaA,    AbA,    Aλ,BaB,    BbB,    Bλ,illustrated in Figure 4 is a labeled state machine and N4where M={μ}and μ(p0)=1for allμ(p)=0, then

pP-{p0}E23

Figure 4.

A labeled state machine L(G4)={ww|w∈{a,b}*}∈SMλ(λ,t).

Example 5 Let N4be a MG controlled grammar where G5=({S,A,B},{a,b},S,R,N5,γ',M')is as for the grammar Rin Example 4, a labeled marked graph G1is illustrated in Figure 5 and N5where M'={μ}for allμ(p)=0. Then

pPE24

Figure 5.

A labeled marked graph L(G5)={ww'|w∈{a,b}*andw'∈Perm(w)}∈MGλ(λ,t).

We have the same result on the labeling strategies as that in the previous section: the labeling of transitions of special Petri nets do not effect on the generative powers of the families of languages generated by grammars controlled by these nets.

Theorem 10 ForN5, andX{SM,GSM,MG,GMG,CN,FC,EFC,AC,ON},

y{r,t,g}E25

The following theorem shows the relations of families of languages generated by special Petri net controlled grammars.

Theorem 11 The following inclusions and equalities hold:

  1. X[λ](f,y)=X[λ](-λ,y)=X[λ](λ,y).E26
  2. MG[λ](x,y)=GMG[λ](x,y)  and  PN(x,y')=X(x,y'),E27
  3. CN(x,y')MG(x,y')PN(x,y')MATλ,E28
  4. MATGSM(x,y')PN(x,y')MATλ,E29
  5. CFMAT=SM(x,y)VECGSM(x,t)CN(x,t)MG(x,t)MATλ,E30

whereMATλ=PNλ(x,y)=PN(x,t)=Xλ(x,t)=Yλ(x,t)=Zλ(x,y),, x{f,-λ,λ}, y{r,g,t}andy'{r,g},  X{FC,EFC,AC,ON},Y{MG,GMG,CN}.

6. Capacity-bounded grammars

In this section we continue the research in this direction by restricting to (context-free, extended or arbitrary) Petri nets with place capacities. Quite obviously, a context-free Petri net with place capacity regulates the defining grammar by permitting only those derivations where the number of each nonterminal in each sentential form is bounded by its capacity. Similar mechanisms have been introduced and investigated by several authors. Grammar with finite index (the index of a grammar is the maximal number of nonterminals simultaneously appearing in its complete derivations (considering the most economical derivations for each string)) were first considered by Brainerd [7]. Nonterminal-bounded grammars (a grammar a nonterminal-bounded if the total number of nonterminals in every sentential form does not exceed an upper bound) were introduced by Altman and Banerji in [3, 4, 5]. A “weak” variant of nonterminal-bounded grammars (only the complete derivations are required to be bounded) were defined by Moriya [44]. Ginsburg and Spanier introduced derivation-bounded languages in [32] (all strings which have complete derivation in a grammar Z{SM,GSM,FC,EFC,AC,ON}consisting of sentential forms each of which does not contain more than Gnonterminals collected in the setk). There it was shown that grammars regulated in this way generate the family of context-free languages of finite index, even if arbitrary nonterminal strings are allowed as left-hand sides of production rules. Finite index restrictions to regulated grammars have also been investigated [29, 30, 48, 49, 51, 53, 54, 55]. There it was shown that the families of most regulated languages are collapse.

In this section we show that capacity-bounded context-free grammars have a larger generative power than context-free grammars of finite index while the family of languages generated by capacity-bounded phrase structure grammars (due to Ginsburg and Spanier) and several families of languages generated by grammars controlled by extended cf Petri nets with place capacities coincide with the family of matrix languages of finite index.

We will now introduce capacity-bounded grammars and show some relations to similar concepts known from the literature.

Definition 9 A capacity-bounded grammar is a tuple Lk(G)where G=(V,Σ,S,R,κ)is a grammar and G'=(V,Σ,S,R)is a capacity function. The derivation relation κ:VNis defined as Giff αGβand αG'βand|α|Aκ(A), for all|β|Aκ(A). The language of AVis defined asG.

The families of languages generated by capacity-bounded GS grammars and by context-free capacity-bounded grammars are denoted by L(G)={wΣ*|SG*w}andGScb, respectively. The capacity function mapping each nonterminal to CFcbis denoted by1. The notions of finite index and bounded capacities can be extended to matrix, vector and semi-matrix grammars. The corresponding language families are denoted by

1E31

Capacity-bounded grammars are very similar to derivation-bounded grammars, which were studied in [32]. A derivation-bounded grammar is a quintuple MATfin[λ],  VECfin[λ],  sMATfin[λ],  MATcb[λ],  VECcb[λ].where G=(V,Σ,S,R,k)is a grammar and G'=(V,Σ,S,R)is a bound on the number of allowed nonterminals. The language of kNcontains all words Gthat have a derivation wL(G')such thatS*w, for each sentential form |β|Vkof the derivation.

Other related concepts are nonterminal-bounded grammars and grammars of finite index. A context-free grammar βis nonterminal-bounded if G=(V,Σ,S,R)for some fixed |β|Vkand all sentential forms kNderivable inβ. The index of a derivation in Gis the maximal number of nonterminal symbols in its sentential forms. Gis of finite index if every word in Ghas a derivation of index at most L(G)for some fixedk. The family of context-free languages of finite index is denoted bykN.

Note that there is a subtle difference between the first two and the last two concepts. While context-free nonterminal-bounded and finite index grammars are just context-free grammars with a certain structural property (and generate context-free languages by definition), capacity-bounded and derivation-bounded grammars are special cases of regulated rewriting (and could therefore generate non-context-free languages). However, it has been shown that the family of derivation bounded languages is equal toCFfin, even if arbitrary grammars due to Ginsburg and Spanier are permitted [32]. We will now give an example of capacity-bounded grammars generating non-context-free languages.

Example 6 Let CFfinbe the capacity-bounded grammar where G=({S,A,B,C,D,E,F},{a,b,c},S,R,1)consists of the rules:

RE32

The possible derivations are exactly those of the form

r1:SABCD,r2:ABaEFb,r3:CDcAD,r4:EFEC,r5:EFFC,r6:ADFD,r7:ADED,r8:ECAB,r9:FDCD,r10:FCAF,r11:AFλ,r12:EDλ.E33

(in the last phase, the sequences Sr1ABCD(r2r3r4r6r8r9)nanABbncnCDr2r3an+1EFbn+1cn+1ADr5r7an+1FCbn+1cn+1EDr10r11r12anbncnand r10r12r11could also be applied with the same result). Therefore,

r12r10r11E34

The above example shows that capacity-bounded grammars – in contrast to derivation bounded grammars – can generate non-context-free languages. Moreover, any context-free language generated by a grammar of L(G)={anbncn|n1}.of finite index is also generated by the capacity-bounded grammar Gwhere (G,κ)is capacity function constantlyκ.

Let kand CFcb1be the language families generated by context-free and arbitrary grammars with capacity functionGScb1. Then,

Lemma 12 1andCFcb=CFcb1.

On the other hand, capacity-bounded GS grammars generate exactly the family of matrix languages of finite index. This is in contrast to derivation bounded grammars which generate only context-free languages of finite index [32].

Lemma 13GScb=GScb1.

It turns out that capacity-bounded context-free grammars are strictly between context-free languages of finite index and matrix languages of finite index.

Theorem 14 GScb=MATfin

The next theorem shows that the families of capacity bounded matrix and vector languages are exactly the family of matrix languages with finite index.

Theorem 15CFfinCFcbGScb=MATfin..

As regards closure properties, we remark that the constructions showing the closure of MATfin=VECcb[λ]=MATcb[λ]under homomorphisms, union, concatenation and Kleene closure can be easily extended to the case of capacity-bounded languages.

Theorem 16 CFis closed under homomorphisms, union, concatenation and Kleene closure.

Regarding intersection with regular sets and inverse homomorphisms, we can show non-closure properties.

Theorem 17 CFcbis neither closed under intersection with regular sets nor under inverse homomorphisms.

Control by Petri nets can in a natural way be adapted to Petri nets with place capacities. A context-free grammar is controlled by its context-free Petri net with place capacity by only allowing derivations that correspond to valid firing sequences respecting the capacity bounds. The (trivial) proof for the equivalence between context-free grammars and grammars controlled by cf Petri nets can be immediately transferred to context-free grammars and Petri nets with capacities:

Theorem 18 Grammars controlled by context-free Petri nets with place capacity functions generate the family of capacity-bounded context-free languages.

Let us now turn to grammars controlled by arbitrary Petri nets with capacities. Let CFcbbe an arbitrary Petri net controlled grammar. G=(V,Σ,S,R,N,γ,M)is called a grammar controlled by an arbitrary Petri net with place capacity if Gis a Petri net with place capacity. The families of languages generated by grammars controlled by arbitrary Petri nets with place capacities (with erasing rules) is denoted by N(PNcb(x,y)) where PNcbλ(x,y)andx{f,-λ,λ}.

The next statement indicates that the language generated by a grammar controlled by an arbitrary Petri net with place capacities iff it is generated by a matrix grammar (for details, see [56]).

Theorem 19 For y∈{r,t,g}andx{f,-λ,λ},

y{r,t,g}E35

We summarize our results in the following theorem.

Theorem 20 The following inclusions and equalities hold:

PNcb(x,y)=MATPNcbλ(x,y)=MATλ.E36
CFfinCFcb=CFcb1E37
MATfin=MATcb[λ]=VECcb[λ]=GScb=GScb1E38

where MAT=PNcb(x,y)MATλ=PNcbλ(x,y)andx{f,-λ,λ}.

7. Conclusions and future research

The chapter summarizes the recent results on Petri net controlled grammars presented in [18, 19, 20, 21, 22, 23, 56, 59, 60, 61, 62] and the close related topic: capacity-bounded grammars. Though the theme of regulated grammars is one of the classic topics in formal language theory, a Petri net controlled grammar is still interesting subject for the investigation for many reasons. On the one hand, this type of grammars can successfully be used in modeling new problems emerging in manufacturing systems, systems biology and other areas. On the other hand, the graphically illustrability, the ability to represent both a grammar and its control in one structure, and the possibility to unify different regulated rewritings make this formalization attractive for the study. Moreover, control by Petri nets introduces the concept of concurrency in regulated rewriting systems.

We should mention that there are some open problems, the study of which is of interest: one of them concerns to the classic open problem of the theory of regulated rewriting systems – the strictness of the inclusiony{r,t,g}. We showed that language families generated by (arbitrary) Petri net controlled grammars are between the families MATMATλandMAT. Moreover, the work [65] of G. Zetzsche shows that the erasing rules in Petri net controlled grammars with finite set of final markings can be eliminated without effecting on the generative power, which gives hope that one can solve this problem.

There is also another very interesting topic in this direction for the future study. If we notice the definitions of derivation-bounded [32] or nonterminal-bounded grammars [3, 4, 5] only nonterminal strings are allowed as left-hand sides of production rules. Here, an interesting question is emerged, what kind of languages can be generated if we derestrict this condition, i.e., allow any string in the left-hand side of the rules?

In all investigated types of Petri net controlled grammars, we only used the sequential firing mode of transitions. The consideration of simultaneous firing of transitions, another fundamental feature of Petri nets, opens a new direction for the future research: one can study grammars controlled by Petri nets under parallel firing strategy, which introduces concurrently parallelism in formal language theory.

Grammar systems can be considered as a formal model for a phenomenon of solving a given problem by dividing it into subproblems (grammars) to be solved by several parts in turn (CD grammar systems) or in parallel (PC grammar systems). The control of derivations in grammar systems also allows increasing computational power grammar systems. We can extend the regulation of a rule by a transition to the regulation a set of rules by a transition, which defines a new type of grammar systems: the firing of a transition allows applying several (assigned) rules in a derivation step parallelly and different modes.

In [19, 20, 21, 22, 41, 62] it was shown that by adding places and arcs which satisfy some structural requirements one can generate well-known families of languages as random context languages, valence languages, vector languages and matrix languages. Thus, the control by Petri nets can be considered as a unifying approach to different types of control. On the other hand, Petri nets can be transformed into occurrence nets, i.e., usually an infinite, tree-like structure whose nodes have the same labels as those of the places and transitions of the Petri net preserving the relationship of adjacency, using unfolding technique introduced in [43] and given in [24] in detail under the name of branching processes. Any finite initial part, i.e., prefix of the occurrence net of a cf Petri net can be considered as a derivation tree for the corresponding context-free grammar as it has the same structure as a usual derivation tree, here we can also accept the rule of reading “leaf”-places with tokens from the left to the right as in usual derivation trees. We can also generalize this idea for regulated grammars considering prefixes of the occurrences nets obtained from cf Petri nets with additional places. Hence, we can take into consideration the grammar as well as its control, and construct (Petri net) derivation trees for regulated grammars, which help to construct effective parsing algorithms for regulated rewriting systems. Though the preliminary results (general parsing algorithms, Early-like parsing algorithm for deterministic extended context-free Petri net controlled grammars, etc.) were obtained in [63, 64], the problem of the development of the effective parsing algorithms for regulated grammars remain open.

Acknowledgement

This work has been supported by Ministry of Higher Education of Malaysia via Fundamental Research Grant Scheme FRGS /1/11/SG/UPM/01/1 and Universiti Putra Malaysia via RUGS 05-01-10-0896RU/F1.

© 2012 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution 3.0 License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

J. Dassow, G. Mavlankulov, M. Othman, S. Turaev, M.H. Selamat and R. Stiebe (August 29th 2012). Grammars Controlled by Petri Nets, Petri Nets - Manufacturing and Computer Science, Pawel Pawlewski, IntechOpen, DOI: 10.5772/50637. Available from:

chapter statistics

1552total chapter downloads

2Crossref citations

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

Related Content

This Book

Next chapter

Timed Petri Nets

By José Reinaldo Silva and Pedro M. G. del Foyo

Related Book

First chapter

An Application of GSPN for Modeling and Evaluating Local Area Computer Networks

By Masahiro Tsunoyama and Hiroei Imai

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us