Abstract: It has been proved that regular language is a subclass of Petri net languages. Standard properly end Petri net, a subclass of Petri nets is defined in the related references, and the equivalency between a standard properly end Petri net and a regular language has been investigated. Thus, the Petri net constructing methods of Kleene closure operations with and without an ε-empty label in regular expressions are presented respectively in this study. By the methods, the net model of producing regular language L* can be constructed from that of producing regular language L. It is proved that a standard properly end Petri net language of Kleene closure operations is close.
INTRODUCTION
As an important part of Petri nets (PN), PN language plays an important role in the description and analysis of system behavior (Du et al., 2007; Zeng and Duan, 2007; Scarpelli et al., 1996; Zeng, 2007). Some good research achievements of PN languages have been made. The relation between PN languages and Chomsky formal languages was analyzed (Peterson, 1981; Murata, 1989). The conceptions of a vector grammar and PN machines were presented, and the relations between vector grammar and PN language and between PN machine and PN languages were investigated (Jiang, 1996). A necessary and sufficient condition of whether a PN is a regular language or a context-free language was obtained based on the Pumping lemma in PNs. The Pumping lemma describes the commonness of PN language and by it we can prove that some languages could not be produced by PNs (Wu, 1994; Jiang and Lu, 2006; Wang et al., 2000).
How to create a PN with a known language expression or a language set? This problem is discussed few at present. The method of transferring a concurrence expression to a safe labeled PN was represented (Du et al., 2008). A subclass of PNs, the standard properly end PNs, was proposed and the equivalency between standard properly end PNs and regular languages has been proved (Lian et al., 2008). This research investigates mainly the constructing methods of Kleene closure operations in regular languages based on PNs. For a regular language L(N) produced by net N, we can construct a net model which produces language L(N)*. However, it`s difficult to construct a language closure operation based on PNs, since some part of a PN model is repeatedly used and some positions may be not empty before they are used again during the construction process. According to the properties of standard properly end PNs, the PN methods of constructing closure operations in regular language are well resolved. Thus, the PN methods of constructing a kleene closure operation with and without an ε-empty label are presented in this paper. We prove that the closure operation in standard properly end PNs is close. That is, if L(N) is a formal language produced by a standard properly end PN, the PN model of producing language L(N)* is also a standard properly end PN.
BASIC CONCEPTS AND TERMS
Some basic concepts and properties of PNs are simply reviewed in this section and other concepts of PN languages can be referred by Peterson (1981) and Murata (1989).
Definition 1: (Peterson, 1981; Murata, 1989): Let N = (P,T;G,M0,Σ,h,F) be a labeled PN, where (P,T;G,M0) is a PN, G⊆(PxT)∪(TxP) is flow relation of PN, Σ is a finite alphabet, h:T→Σ is a labeled function, F is an end state set, then
L(N) = {α ∈Σ*|∃σ ∈T* >vM0[σ>M>vM ∈F>vh(σ) = α} is a language produced by the PN.
L(N) is called an L-type language produced by N if F is any subset of R(M0). According to different situations of labeled function h:T-Σ, there are three types of PN languages, i.e., PN languages without labeled languages, with and without an ε-empty label language. We mainly investigate the standard properly end Petri net methods of constructing closure operations with and without an ε-empty label in regular languages in this study.
Definition 2: Peterson (1981): Let N = (P,T;G,M0,Σ,h,F) be a labeled Petri net, it produces language L(N). It is called a standard Petri net if it satisfies the following conditions.
| • | ∃ ps, pf ∈ P, such that Ps = φ and pf = φ. ps is called a start position, pf is called an end position. |
| • | The initial marking M0 satisfies |
| • | Any transition will not be enabled once there exists a token in end position pf. |
| • | There is a marking Mf such that If λ ∈ L(N), then F = {M0, Mf}, else F {Mf}. |
Theorem 1: Peterson (1981): Let L be any Petri net language; there exists a standard Petri net which produces languageL.
Definition 3: Lian et al. (2008): Let N = (P,T;G,M0,Σ,h,F) be a standard Petri net, if >∀M ∈R(M0): M(Pf) = 1→∀p ∈P>!{pf}: M(p) = 0, then N is a standard properly end Petri net.
Definition 4: Lian et al. (2008): If N is a standard properly end Petri net, then L(N) = {α ∈Σ*|∃σ ∈T* >vM0[σ >Mf >vh(σ) = α} is called a language produced by N.
Theorem 2: Lian et al. (2008): Standard properly end Petri nets must be bounded Petri nets.
Theorem 3: Lian et al. (2008): A standard properly end Petri net language is equivalent to a regular language.
Definition 5: John et al. (2004): Let L1, be a language in alphabet Σ. Kleene closure operation * is defined as follows:
where, L10 = {λ} and λ is an empty string.
PN METHOD OF CONSTRUCTING KLEENE CLOSURE OPERATIONS
Differences between standard properly end PNs and standard PNs: Standard properly end Petri nets are more special than common standard Petri nets from definitions 2 and 3. This can be illustrated with Fig. 1. In Fig. 1a, N1 is a standard Petri net, but not a standard properly end Petri net. Since there exists σ = εaaεbε and M0[σ>M', where
it doesn`t satisfy >∀M ∈R(M0): M(Pf) = 1→∀p ∈P>!{pf}: M(p) = 0.
In Fig. 1b, N2 is a standard properly end Petri net, and it can be seen when there exists a token in pf. There isn`t any transition which can be fired and there is not any place which includes redundant tokens. When N2 stops running (no transition can be fired), therefore, it is in an acceptable state Mf. Thus N2 is called a properly end net.
In Fig. 1a, the language produced by net N1 is L(N1) = anbn and the net is in an acceptable state Mf, where
Although a transition sequence σ = εaaεbε can be fired by net N1 and the net stops running at state M', where
M' is not the acceptable state of net N1, there is redundant token in p2, M'(p2) = 1, thus, h(σ) = h(εaaεbε) = aab >ó L(N1) Similarly, closure operation * in Petri net languages is not close.
| Fig. 1: | Standard PNs and standard properly End PNs, (a) Standard
Petri Net N1 L(N1) = {anbn|n≥0}
and (b): Standard properly end Petri Net N2 L(N2)
= (a+b)+ |
| Fig. 2: | Net N3 |
| Fig. 3: | Model of an abstract standard properly end petri net |
When the structure of net N1 is used repeatedly to produce language L(N1)* = (anbn)*,
it can`t ensure some positions or position sets be empty before they`re
used again, such as p2 in Fig. 2. For net
N2, there exists M0[σ>Mf, where
Petri net (with ε-empty label) method of constructing closure operation: For convenience, an abstract standard properly end Petri net can be represented in Fig. 3. ps, pf are a start position and an end position, respectively. Tin = {t|t ∈ ps∪ is a start transition set and Tout = {t|t ∈Cpf is an end transition set.
Theorem 4: Let N1 = (P1,T1;G1,M01,Σ,h1,F1) be a standard properly end Petri net, it produces a language L(N1). Then there exists a standard properly end Petri net N = (p,T;,G,M0,Σ,h,F) with an ε-empty label, such that the net produces a language L(N) = (L(N1))*.
Proof: Construct a net N from N1 (Fig. 4), Let L(N) = (L(N1))* be a language produced by N. Add two new places ps, pf as a start position and an end position of N, respectively. In order to produce Kleene closure *, we introduce four transitions tk1,tk2,tk3,tk4 with an empty label. Therefore, we have N = (P,T;G,M0,Σ,h,F), where
| Fig. 4: | Net N: L (N) = (L (N1))* |
L(N) = (L(N1))* is proved as follows.
If a transition sequence set N1(σ) is defined by
.According to Fig. 4, there exist only three transition firing ways which can transfer a token from ps to pf.
| (a) | h(tk2) ∈ L(N) and ε ∈ L(N) since M0[tk2>Mf. |
| (b) | M0[tk1>Ms1[σ>Mf1[tk4>Mf, where σ ∈ N1(σ).Let α = h1(σ), then α ∈ L(N1). According to this transition sequence σ, we have h(tk1οσοtk4) ∈ L(N) and h(tk1οσοtk4) = h(tk1)οh1(σ)οh(tk4) = εοαοε = α ∈ L(N). By means of the randomness of σ, L(N1)⊆L(N). |
| (c) | M0[tk1>Ms1[σi1>Mf1[tk3>Ms1[σi2>Mf1[tk3>
>… Ms1[σij>Mf1 [tk4>
>… Mf, where σi1, σi2, >…σij >… are random elements in N1(σ). Let αij = h1(σij) (j = 1,2>…), then αij ∈ L(N1). According to transition sequence tk1οσi1οtk3οσi2οtk3 …οσij…οtk4, we have h(tk1οσi1οtk3οσi2οtk3 …οσij…οtk4) ∈ L(N)
and h(tk1οσi1οtk3οσi2οtk3 …οσij…οtk4) |
According to the randomness of σi1, σi2, …σij…, it`s known that L(N1)k ⊆L(N), where k is positive integer and k≥2. From rules a, b and c, we get L(N1)0∪L(N1)1∪L(N1)2∪… = (L(N1))* ⊆L(N) and L(N) = (L(N1))* since there exits only three firing ways in net N. Therefore, N is a standard properly end Petri net and L(N) = (L(N1))* based on the structure of N and the previous proof.
Petri net (without ε-empty label) method of constructing closure operation: It`s more difficult to construct a Petri net model without ε-empty label, since a net structure must be reused. In the following, we discuss primarily how to construct a Petri net model without an ε-empty label of the closure operation of regular languages.
Theorem 5: Let N1 = (P1,T1;G1,M01,Σ,h1,F1) be a standard properly end Petri net without an ε-empty label, it produces a language L(N1). Then there exists a standard properly end Petri net N = (P,T;G,M0,Σ,h,F), its labeled function h is without an ε-empty label and it produces a language L(N) = (L(N1))*.
Proof: Construct two new places ps, pf in N and they are used as a start position and an end position respectively. The structure of N1 will be repeatedly used for 4 times to produce the kleene closure (*) of L(N1). The structure of N = (P,T;G,M0,Σ,h,F), is shown in Fig. 5 in detail and some unnecessary processes are omitted. From λ ∈(L(N1))*, F = {M0,Mf} is the end marking set of N.
The proof of L(N) = (L(N1))* is given as follows.
For convenience, some markings of net N are defined as
According to the construction of net N, there exist only three ways of transferring a token from ps to pf. Therefore, three types of transition firing sequences are analyzed as follows.
| (a) | M0[σ>Mf, where σ is any transition sequence in N1(σ). Then L(N1)⊆L(N). |
| Fig. 5: | Net N: L (N) = (L (N1))* |
| (b) | M0[σ1>Mrep[σ2>Mf, where σ1, σ2 ∈ N1(σ). Then L(N1) οL(N1)⊆L(N). |
| (c) | M0[σ1>Mrep[σi1>Mrep[σi2>Mrep…M[σij>…Mrep[σ2>Mf, where σ1, σ2 σi1, σi2… are random transition sequences in N1(σ). Then L(N1)k⊆L(N). where k is a positive integer and k≥2. |
According to cases a), b) and c), we have L(N1)1∪L(N1)2∪… = (L(N))* ⊆L(N). From M0 ∈ F, then L(N1)0 = {λ} ⊆ L(N) and L(N) = (L(N1))*. Therefore, N is a standard properly end Petri net by means of the structure of N and the previous proof.
EXAMPLES: With the respect to PNs with an ε-empty label and without an ε-empty label, Theorems 4 and 5 show respectively the PN methods of constructing kleene closure operation * in regular language. The use of the constructing methods is illustrated with the following examples.
Example 1: Let Σ = {a,b} and net N1 = (P1,T1; G1,M01,Σ,h1,F1) be a standard properly end Petri net. The structure of N1 is shown in Fig. 6a and it produces a language L(N1) = ab. Construct a standard properly end Petri net N with an ε-empty label and L(N) = (L(N1))* = (ab)*.
According to Theorem 4, a standard end Petri net N with an ε-empty label can be constructed in Fig. 6b. We can easily verify that it satisfies L(N) = (L(N1))* = (ab)*.
Example 2: Let Σ = {a,b} and net N1 = (P1,T1; G1,M01,Σ,h1,F1) be a standard properly end Petri net. Net N1 is shown in Fig. 6a and it produces a language L(N1) = ab. Construct a standard properly end Petri net N without an ε-empty label and L(N) = (L(N1))* = (ab)*.
| Fig. 6: | (a) Net N1 and (b): Net N |
| Fig. 7: | Net N |
According to Theorem 5, a standard end Petri net N without an ε-empty label can be constructed in Fig. 7. We can easily check it satisfies L(N) = (L(N1))* = (ab)*.
CONCLUSIONS
Petri net languages play an important role in system behavior description and analysis. It is a fact that many operations of PN languages are close, such as connection, union, reverse, permutation operations. However, a closure operation is not close. It means that there is a net N which produces a language L(N), but the language (L(N))* is not a Petri net language. Standard properly end PNs are seen as a subclass of PNs in this paper, and its language is a regular language. We prove that closure operation of standard properly end Petri nets is close. Given a standard properly end Petri net N1 producing a language L(N1), therefore, a standard properly end Petri net N can be constructed and it produces a language (L(N1))*. The Petri net with and without an ε-empty label methods of constructing closure operations in regular language are proposed explicitly, and the methods are illustrated with corresponding instances. This work has an important value to investigate further the Petri net language theory and applications.
ACKNOWLEDGMENTS
This study was supported in part by the National Natural Science Foundation of China under Grants 60773034, 60673053, 60603090, 60534060 and 60473094; the Taishan Scholar Construction Project of Shandong Province, China; the National Basic Research Program of China (973 Program) under Grants 2003CB316902, 2007CB316502 and 2004CB318001-03 and the Open Project of the State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences under Grant SYSKF0604.