数理解析研究所講究録
第 1799 巻 2012 年 49-56

49

Variants of Petri net controlled grammars and their parsing algorithms
Taishin Yasunobu Nishidal
Department of Information Sciences
Toyama Prefectural University
Abstract
We show an outline of three parsing algorithms for three variants of Petri net controlled
grammars. Time complexities of these algorithm vary $hom$ deterministic polynomial time tonondeterministic polynomial time. These algorithms only parse grammars without -rules andcyclic rules.
$\lambda$

1

Introduction and preliminaries

Recently Petri net controlled grammars have been introduced by M. ter Beek and J. Kleijn [1].
Then J. Dassow and S. Turaev have defined a number of variants of Petri net controlled gramnars
and they have investigated properties of languages generated by these variants [3, 4, 5, 6, 12]. But
parsing algorithms for Petri net controlled grammars have not been considered.
In this extended abstract, we introduce some variants of Petri net controlled grammars andparsing algorithms for them. The simplest class, yet generates non-context-free languages, has aparsing algorithm of deterministic polynomial time. We introduce two other classes: one class has aparsing algorithm whose computation time is proportional to multiple of the number of derivation
trees and their size and the other class has a parsing algorithm of nondeterministic polynomialtime.
We assume that the reader is familiar with mdiments of context-free grammars, regulated
grammars, and Petri nets. For notions and notations which are not described in this section, we
refer to [2, 7, 9, 10, 11].

1.1

Context-free grammars

A context-free grammar is a construct $G=(V, \Sigma, S, R)$ where and are nonterminal and terminalalphabets, respectively, with
$S\in V$ is the start symbol, andis a finite
set of (production) rules. A rule $(A, x)$ is written as $Aarrow x$ . A word $x\in(V\cup\Sigma)^{+}$ directly derives$y\in(V\cup\Sigma)^{*}$ ,written as, if and only if there is a rule $r:Aarrow\alpha\in R$ such that $x=x_{1}Ax_{2}$and. We write
if is understood and write
if we are not interested in therule . The reflexive and transitive closure of is denoted by. If there are a sequence of rules
and a sequence of words
such thatfor every $1\leq i\leq n$ , thenwe write. A rule of the form
where is the empty word is called a -rule. A
set of rules
is said to be cyclic rules if
for every $2\leq i\leq n$ and$Q_{n}=A_{1}$ . The language
generated by is defined by $L(G)=\{w\in\Sigma^{*}|S\Rightarrow_{G}^{*}w\}$ .
$V$$\Sigma$$V\cap\Sigma=\emptyset,$$R\subseteq V\cross(V\cup\Sigma)^{*}$$x\Rightarrow cyr$$x\Rightarrow ry$$y=x_{1}\alpha x_{2}$$G$$x\Rightarrow y$$r$$r_{1},$ $r_{2},$$\Rightarrow^{*}$$\Rightarrow$$\ldots,$$r_{n}$$w_{0},$ $w_{1},$$w_{0}^{\underline{\underline{r_{1}r_{2}r}}},$$\ldots,$$Aarrow\lambda$$w_{n}$$w_{i-1}\dot{\neq}^{r}w_{i}$$w_{n}$$\lambda$$\lambda$$\{A_{1}arrow\alpha_{1}, \ldots, A_{n}arrow\alpha_{n}\}$$\alpha_{i-1}=A_{i}$

$G$

1.2

Petri net

A Petri net is a quadruple $N=(P, T, F, \phi)$ where $P$ and are disjoint finite sets of places andtransitions, respectively, $F\subseteq(P\cross T)\cup(T\cross P)$ is the set of directed arcs, : $(P\cross T)\cup(T\cross P)arrow$ lN
is a weight function with $\phi(x, y)=0$ for every $(x, y)\not\in F$ , where $N$ is the set of nonnegative integers.
A Petri net can be represented by a bipartite directed graph with the node set $P\cup T$ where places$T$$\phi$

lemail: nishida@pu-toyama.ac.jp

50
are drawn as circles, transitions are rectangles, and arcs as arrows with labelsor$\phi(p,t)$$\phi(t,p)$. If

or $\phi(t,p)=1$ , then the. label is omitted.
A place contains a number of tokens. Each number of tokens in every place is expressed by adenotes the number ofmapping : $Parrow N$ , which is called a marking. For every place $p\in P,$
circles.
dots
inside
small
solid
as
drawn
Graphically,.
tokens aretokens in
A transition $t\in T$ is enabled by a marking if and only if $\mu(p)\geq\phi(p,t)$ for every $p\in P$ . In
this case can occur (fire). An occurrence of a transition transforms the marking into a newmarking
which is defined by $\mu’(p)=\mu(p)-\phi(p, t)+\phi(t,p)$ for every $p\in P$ . More than one
transition may be enabled by a marking. In this case one transition is nondeteministically selected
and fires. If a transition occurs in a marking and the marking changes to , then we writeof transitions is called an occurrence sequence enabled at a
. A finite sequence. In short this sequencesuch that
if there are markings
markin$1\leqi\leq k$ , the marking. For eachwhereor
can be written as$N=(P,T,
F_{\tau}\phi, \iota)$ whereis called reachable from the marking . A marked Petri net is a system$(P, T, F, \phi)$ is a Petri net,is the initial marking.
Let $N=(P,T, F, \phi)$ be a Petri net. For an arc $e=(u, v)$ in $F$ (note that $(u\in P$ and $v\in T)$ oris$(u\in T$ and $v\in P))$ , we use the notations $e=u$ and $e=v$ . A sequence of arcs
.
$N$
if
cycle
$i\in\{1,\ldots,n-1\}$apath$e_{n}=e_{1}$
.
A
is
every
for
said to be a path inif$\phi(p,t)=1$$\mu(p)$

$\mu$

$p$

$\mu$

$t$

$t$

$\mu$

$\mu’$$t$$\muarrow t\mu’$$\mu’$$\mu$$t_{1}t_{2}\cdots t_{k}$$\muarrow\mu_{1}t_{1}arrow t_{2}\ldotsarrow\mu_{k}t_{k}$$g\mu$$\mu_{1},$$\mu^{t_{1}t_{2}\cdots t_{k}}arrow\mu_{k}$$\mu_{2},$$\ldots,$$\mu_{k}$$\nu=t_{1}t_{2}\cdots t_{k}$$\muarrow\nu\mu_{k}$$\mu_{i}$$\mu$$\iota$$e_{1},$ $e_{2},$$\ldots,$$e_{n}$$e_{\dot{i}}=e_{i+1}$

2

Petri net controlled grammars

In this section we define Petri net controlled grammars.
Let $G=(V, \Sigma, S, R)$ be a context-free grammar. A marked Petri net $N=(P, T, F, \phi, \iota)$ is a $cf$
satisfy:
if $N$ andPetri net with respect to under labellin functions$G$(1) $\beta:Parrow V$ and(2) $F$ and$\phi$$\gamma$$(\beta,\gamma)$$g$$(\beta, \gamma)$: $Tarrow R$ are bijections.

satisfy:$-(p,t)\in F$ if and only if $\gamma(t)=Aarrow\alpha$ and $\beta(p)=A$ , in this case $\phi(p,t)=1$ .

$-(t,p)\in F$ if and only if $\gamma(t)=Aarrow\alpha$ and $\beta(p)=x$ where$\phi(t,p)=|\alpha|_{x}$$|\alpha|_{x}\geq 1$.

, in this case

(3) $\iota(p)=1$ if $\beta(p)=S$ and $\iota(p)=0$ for every $p\in P-\{\beta^{-1}(S)\}$ .

-free granmar
We note that a cf Petri net is uniquely determined from a combination of a
. Therefore, a cf Petri net with respect to under
and a pair offunctionscan be denoted by $PN[G, (\beta,\gamma)]$ .
$\infty ntext$$G$$labe\mathbb{I}\dot{m}g$$G$$(\beta,\gamma)$$(\beta, \gamma)$

Definition 1 Let $G_{0}=(V, \Sigma, S, R)$ be a context-free grammar and let $N=PN[G_{0}, (\beta,\gamma)]=$$(P,T, F, \phi, \iota)$ be a $cf$ Petri net vrith respect to.
Petri net controlled grammar is a quin$S,$
and
are the components from the grammar
tuple $G=(V, \Sigma, S, R, N)$ where $V,$
$N=(P’,T’, F’, \phi’, \iota’)$ is a Petri net which satisfies:$G_{0}$$\Sigma,$

$A$

$R$

$G_{0}$(1) $P’=P\cup Q$ where $Q=\{q_{1}, \ldots, q_{k}\}$ is a set of new places.

(2) $T’=T$ .

of new arcs which satisfy, for every $1\leq i\leq k$ ,$(t’,q_{i})\in E$$t\in T$
only
and
some
for some $t’\in T$ ,
if
if
for

$(S)F’=F\cup E$ where $E\subseteq(T\cross Q)\cup(Q\cross T)$ is a set$(q_{i}, t)\in E$

51(4) $\phi’(x,y)=\phi(x,y)$ if $(x,y)\in F$ and $\phi’(x,y)=1$ if $(x,y)\in E$ .
(5) $\iota’(p)=1$ if $\beta(p)=S$ and $\iota’(p)=0$ for every $p\in(P-\{\beta^{-1}(S)\})\cup Q,$ $i,e.,$ $\iota’(p)=\iota(p)$ if$p\in P$ and $\iota’(p)=0\iota fp\in Q$ .

We call$G_{0}$

the underlying grammar of$G$.

Let be the marking $\tau(p)=0$ for every $p\in PUQ$ . Next we define the derivation in a Petri net
controlled grammar and the language generated by .
$\tau$$G$$G$

Definition 2 Let $G=(V, \Sigma, S, R,N)$ be a Petri net controlled grammar. A wordisderived in if
such thatis an occurrence sequence
successfullyof the tmnsitions of $N$ enabled at the initial marking A derivation
generates a terminal word if
is an occurrence sequence of thetransitions of $N$ enabled at the initial marking and finished at the marking . The language
generated by , denoted by $L(G)$ , consis of all words which are successfully genemted in .
$\alpha\in(V\cup\Sigma)^{*}$$G$$S^{\underline{\underline{r_{1}r_{2}r}}},$$t_{1}t_{2}\cdots t_{n}=\gamma^{-1}(r_{1}r_{2}\cdots r_{n})\in\tau*$$\alpha$$S^{r_{1}r_{2}}arrow^{r}w\in\Sigma^{*}$$\iota.$$t_{1}t_{2}\cdots t_{n}=\gamma^{-1}(r_{1}r_{2}\cdots r_{n})\in\tau*$$\tau$$\iota$

$G$

$ts$

$G$

Adding conditions on the set $E$ of new arcs, we define the next variants of Petri net controlled
grammars.

Figure 1: A $tcPN$ controlled grammar generating $\{ww|w\in\{a, b\}^{+}\}$ .

.
.

If the set of new arcs satisfies

for every $t\in T$ if $(q,t)\in E$ and $(q’,t)\in E$ for somefor every $t\in T$ if $(t, q)\in E$ and $(t, q’)\in E$ for some$q,$$q’\in Q$, then $q=q’$ and$q,$$q’\in Q$, then $q=q’$ ,then the grammar is said to be a token conserving Petri net controlled gramnar, abbreviated toa $tcPN$ controlled grammar. The condition restricts for every transition to have at most one arc toa place in and at most one arc &om a place in .
$G$

$Q$

$Q$

52
Example 1 Let $G_{1}=(\{S,A,B,B’\}, \{a,b\}, S, R, N)$ be a $tcPN$ controlled grammar where $R$ and$N$ is illustrated in Figure 1
in which ndes are draan in the rectangles of the corresponding transitions and arcs between transitions and control places are drawn in dashed lines. The gmmmar
generates the language $\{ww|w\in\{a,b\}^{+}\}$ .
$G_{1}$$\square$If the set of new arcs of a $tcPN$ controlled grammar satisfies that, for every $1\leq i<j\leq k$ , there
exists no $t\in T$ such that $(t,q_{i})\in E$ and $(q_{j}, t)\in E$ , then the grammar is said to be a counter
restricted Petri net controlled grammar, or a $crPN$ controlled grammar for short. The condition
says that there are no cycles composed of places from , that is, places from only count number
of applications of specific rules. The definition of $crPN$ controlled grammars is identical to that ofk-Petri net controlled grammars in [3, 6].
$G$

$Q$

$Q$

$S\varphi\bullet$$q$

Figure 2: A scfPN controlled grammar generating $\{a^{n}b^{n}c^{n}|n>0\}$ .
If a $crPN$ controlled grammar satisfies “every cycle in $N$ does not contain any places in $Q$ ”,
then the grammar is called a strict cycle free Petri net controlled grammar, or an scfPN controlled grammar for short. A control Petri net of a $crPN$ controlled grammar may have a cycle
in which $t_{i}\in T$ for every $1\leq i\leq n,$ $p_{i}\in P’(=P\cup Q)$ for every$1\leq i\leq n$ , and there exists some $p_{j}\in P$ . A cycle in a control Petri net of an scfPN controlled
grammar must satisfy that no node in any cycle is contained in .
$(t_{1},p_{1}),$ $(p_{1},t_{2}),$$\ldots,$$(p_{n},t_{1})$$Q$

Example 2 (Example 7 of [3]) Let $G_{2}=(\{S,A, B\}, \{a,b,c\},S, R,N)$ be a $scfPN$ controlled
grammar where $N$ is illustrated in Figure 2, The grammar
generates the language $\{a^{n}b^{n}c^{n}|n>$$G_{2}$$0\}$.

$\square$

A Petri net controlled grammar without any condition on the control Petri net $N$ is called abijective Petri net controlled grammar, abbreviated to a $bPN$ controlled grammar, because there isa bijection from the set of transitions to the set of rules.

Example 3 Let $G_{3}=(\{S’, S, A, B, D, E, F\}, \{a, b, c\}, S’, R,N)$ be a $bPN$ controlled grammar where$R$ and $N$.
genemtes the language
are illustrated in Figure 3. The grammar$G_{3}$$\{a^{n}b^{n}c^{n}\}^{+}$$\square$53$q_{3}$

Figure 3: A $bPN$ controlled gramnar generating

3$\{a^{n}b^{n}c^{n}\}^{+}$.

Parsing algorithms

Now we show an outline of three algorithm which parse languages generated by scfPN controlled
grammars, $tcPN$ controlled grammars, and $bPN$ controlled grammars. Before going to the algorithms, it should be noted that the algorithm shown here can parse Petri net controlled grammars
with no -rules and no cyclic rules only.
$\lambda$

3.1

scfPN controlled grammars

A parsing algorithm for scfPN controlled grammars is obtained by adding token counters to the
Earley’s algorithm for (usual) context-free grammars [8]. A token counter is a vector fromwhereis the number of control places (the places in ) and is the set of all integers. The Earley’salgorithm makes a state of the form
. The parsing algorithm forfor a rule
scfPN controlled grammars makes states with token counters by$Z^{k}$$k$$Q$$[Aarrow\alpha\cdot\beta]$$Z$$Aarrow\alpha\beta$(1) For a rule, the state
where $v_{i}=1$ and $v_{j}=0$
has a token counter
for $j\neq i$ if $(\gamma^{-1}(Aarrow\alpha), q_{i})\in E,$ $v_{i}=-1$ and $v_{j}=0$ for $j\neq i$ if $(q_{i}, \gamma^{-1}(Aarrow\alpha))\in E$ , or
$Aarrow\alpha$$v_{i}=0$$(v_{1}, \ldots, v_{k})$$[Aarrow\cdot\alpha]$

for every $1\leq i\leq k$ otherwise.

(2) If a state

is obtained
where
and
and
token counters associated to the states, thenhas the token counter
which the addition is the normal component-wise vector addition.
$[Aarrow\alpha B\cdot\beta]$$hom[Aarrow\alpha\cdot B\beta]\vec{v}_{1}$$[Barrow\gamma\cdot]\vec{v}_{2}$$\vec{v}_{1}$$[Aarrow\alpha B\cdot\beta]$$\vec{v}_{2}$are$\vec{v}_{1}+\vec{v}_{2}$inThe termination condition of the Earley’s algorithm, the state $[S’arrow S\cdot]$ is made as the state
for the input word where $S’$ is a new start symbol with only rule $S’arrow S$ , is modffied to that thestateis made as the state for the input word where is the zero vector in .
$w$$[S’arrow S\cdot]\vec{0}$$\vec{0}$$Z^{k}$

Example 4 In Example 2, the sets of Earley’s states with token counters for the word $w=a^{2}b^{2}c^{2}$are shown in the next table.

54

3.2

$tcPN$ controlled grammars

A parsing algorithm for $tcPN$ controlled grammars makes a derivation net from the derivation tree
which is made by a parsing algorithm (e.g., Earley’s algorithm) for the underlying grammars. Firstthe nodes in a derivation tree which are labelled by terninals are removed. The remaining nodes
labelled by nonterminak and are replaced with mles which rewrite the nonteminals. Finally nodesof control places and arcs between control places and mles are added to the tree. A word generated
by the underlying grammar is generated under the control of the token $\infty naerving$ Petri net if andonly if all arcs between control places and rules in the derivation net form a collection of Eulerianpaths.

Figure 4: An example of a derivation net.
Example 5 In Example 1, the derivation net for the word aabaab is shown in Figure 4.
derivation net has a collection of Eulerian paths.

The$\square$3.3$bPN$ controlled grammars

A parsing algorithm for $bPN$ controlled grammars makes a conditiono) tree for a input word. A
conditional tree is based on the derivation tree for the underlying grammar. A conditional tree
contains infomation of control places in every node as the form of if the node is rewritten by a$\overline{q}_{i}$55rule which has an arc from a place and if the node is rewritten by a rule which has an arc to aplace . Next and is cancelled if they satisfy a condition which is equivalent to the movementof tokens in the control Petri net. A word is generated by a $bPN$ controlled grammar if and only
if the conditional tree for the word is cancelled to an empty tree.
$q_{i}$$q_{j}$$\overline{q}_{i}$$q_{j}$$q_{i}$$S:\lambda$$S:q_{1}$$A:\overline{q}_{2}q_{4}$$A:\overline{q}_{2}q_{3}$$B:q_{4}^{-}q_{2}$$B:\overline{q}_{3}ql$

Figure 5: An example of a conditional tree.
Example 6 In Example 3, the conditional tree for the wordconditional tree can be cancelled to an empty tree.

$a^{2}b^{2}c^{2}abc$

is shown in Figure 5. The$\square$4

Conclusion

We have introduced parsing algorithms for PN controlled grammars. If the underlying grammar
is unambiguous, that is, there is just one derivation tree for every word, then the algorithms for
scfPN controlled grammars and $tcPN$ controlled grammars are effective. For input word of length, the time complexities of the algorithms for scfPN controlled grammars and $tcPN$ controlled
grammams are $O(n^{3})$ . For ambiguous gramnars, the algorithms for scfPN controlled grammars and$tcPN$ controlled grammars are less effective, $O(n^{k+4})$ for scfPN controlled.grammars whereis thenumber of places in and $O(2^{n})$ for $tcPN$ controlled grammars.
On the other hand, the algorithm for $bPN$ controlled grammars is nondeterministic and computes in polynomial time of the length of the input. Of course a deterministic version with exponential time is easily constructed.
Let
be a class of languages generated by $xPN$ controlled grammars where $x\in$ { , tc, cr, scf}.
By definition we have
$n$

$k$

$Q$

$b$

$\mathcal{L}(xPN)$.

$\mathcal{L}(scfPN)\subseteq \mathcal{L}(crPN)\subseteq \mathcal{L}(tcPN)\subseteq \mathcal{L}(bPN)$

It does not known whether some of above inclusions are proper or not. In [4], the most general Petrinet controlled grammars, with no restriction on a Petri net, or equivalently, the mapping $hom$ theset of transitions in the control Petri net to the set of rules is not necessarily bijective, are definedand it has been shown that the class of languages generated by such grammars is equivalent to theclass of languages generated by matrix grammars. Therefore, the class of languages generated by

56$bPN$ controlled grammars is included in the class of matrix grammars. Precise characterization of
the classes shown above is a future work.

References[1] Maurice ter Beek and Jetty Kleijn, Petri net control for grammar systems, in W. Brauer,
H. Ehrig, J. Karhum\"aki, and A. Salomaa (eds.) Formal and Natural Computing, LNCS 2300,
220-243, (Springer, Berlin, 2002).

[2] Jiirgen Daaeow and Gheorghe
Berlin 1989).

$P\dot{a}un$, Regulated rewriting in fomal language theory, (Springer,[3] J\"urgen Dassow and Sherzod Turaev, k-Petri net controlled grammars, in C. Mart\’in-Vide,
F. Otto, and H. Fernau (eds.) LATA 2008, LNCS 5196, 209-220 (Springer, Berlin, 2008).
[4] J\"urgen Dassow and Sherzod Turaev, Petri net controlled grammars: the case of special Petrinets, Joumal of Universal Computer Science, 2808-2835, Vol. 14 (2009).

[5] J\"urgen Dassow and Sherzod Turaev, Petri net controlled grammars: the power of labelmg andfinal markings, Romanian Joumal of Information Science and Technology, 191-207, Vol.12(2009).
[6] J\"urgen Dassow and Sherzod Turaev, Petri net controlled grammars with a bounded number, Vol. 19 (2010).
of additional places, Acta Cybemetica,$609\triangleleft 34$[7] Ren\’e David and Hassan Alla, Petri nets and grafcet: tool for modelling discrete event systems,(Prentice Hall, Hertfordshire, 1992).
[8] Jay Earley, An efficient context-free parsing algorithm, Communications of the ACM, 94-102,
Vol. 13 (1970).
[9] John H. Hopcroft and Jeffrey Ullman, Introduction to automata theory, languages, and computation, (Addison-Wesley, Reading, 1979).

[10] Wolfgang Reisig and Grzegorz Rozenberg (eds), Lectures on Petn nets I: Basic model, LNCS
1491, (Springer, Berlin, 1998).
[11] Grzegorz Rozenberg, Arto Salomaa, Handbook of Formal Languag es vol. 1-3, Springer, Berlm,

1997.

[12] Sherzod Turaev, Petri net controlled grammars, Proc. 3rd Doctoml Workshop on MEMICS2007, 233-240, (Znojmo, Czech Republic, 2007).