Interrelation of Languages of Colored Petri Nets and Some Traditional Languages ()
1. Introduction
Petri Nets (PN) is a graphical tool for the formal description of the flow of activities in complex systems. With respect to other more popular techniques of graphical system representation (like block diagrams or logical trees), PN is particularly suited to represent logical interactions among parts or activities in a system in a natural way.
PN used for modeling real systems is sometimes referred to as Condition/Events nets. Places identify the conditions of the parts of the system (working, idling, queuing, and failing), and transitions describe the passage from one condition to another (end of a task, failure, repair...). An event occurs (a transition fires) when all the conditions are satisfied (input places are marked) and give concession to the event. Occurrence of the event completely or partially modifies the status of the conditions (marking). The number of tokens in a place can be used to identify the number of resources lying in the condition denoted by that place. The following examples illustrate typical situations of interaction of activities arising in system modeling [1,2].
The formal definition of a standard Petri nets:
Petri Net 
pair, where 
is the network structure and 
is the network condition.
In structure C of a P-positions, T-transitions are finite sets. 
are the input and output functions, respectively, where 
are all possible collections (repetitive elements) of P. 
is the function of condition, where 
is the set of integers. We determine (in a known manner) the allowed transitions of Petri Nets and the transitions from one state to another, as well as the set of reachable states [1,2].
Coloured Petri Nets (CPN) is a graphical oriented language for design, specification, simulation and verification of systems [3-8]. It is in particular well-suited for systems that consist of a number of processes which communicate and synchronize. Typical examples of application areas are communication protocols, distributed systems, automated production systems, work flow analysis and VLSI chips.
The CPN language allows the model to be represented as a set of modules, allowing complex nets (and systems) to be represented in a hierarchical manner.
In the classical or traditional Petri Net tokens do not differ from each other, we can say that they are colorless. Unlike standard Petri nets in colored, Petri Net of a position can contain tokens of arbitrary complexity, for example, lists, etc., that enables modeling be more reliable.
2. Definition
The mathematical definition of Colored Petri Net: CPN is a nine-tuple
where:
1) 
is a finite set of non-empty types, also called color sets. In the associated CPN Tool, these are described using the language CPN-ML [9]. A token is a value belonging to a type.
2) P is a finite set of places. In the associated CPN Tool these are depicted as ovals/circles.
3) T is a finite set of transitions. In the associated CPN Tool these are depicted as rectangles.
4) A is a finite set of arcs. In the associated CPN Tool these are depicted as directed edges. The sets of places, transitions, and arcs are pairwise disjoint, that is
.
5) N is a node function. It is defined from A into
. In the associated CPN Tool this depicts the source and sink of the directed edge.
6) C is a color function,
.
7) G is a guard function. It is defined from T into expressions such that:
8) E is an arc expression function. It is defined from A into expressions such that:
where p is the place of 
and 
denotes the multi-set type over the base type
.
9) I is an initialization function. It is defined from P into closed expressions so that:
In the CPN Tool this is represented as initial marking next to the associated place.
The distribution of tokens, called marking, in the places of a CPN determines the state of a system being modeled. The dynamic behavior of a CPN is described in terms of the firing of transitions. The firing of a transition takes the system from one state to another. A transition is enabled if the associated arc expressions of all incoming arcs can be evaluated to a multi-set, compatible with the current tokens in their respective input places, and its guard is satisfied. An enabled transition may fire by removing tokens from input places specified by the arc expression of all the incoming arcs and depositing tokens in output places specified by the arc expressions of outgoing arcs.
One of the most studied simple class of formal languages is the class of Regular languages. It is known that any Regular language is the language of Petri Nets [1,10]. It’s possible to construct Petri Net, which generates
a Context-free language, which is not Regular [1]. Not all the languages of Petri Nets are Context-free, built a network that generates 
a Context-sensitive language, which is not Context-free language [1]. Unlike Regular languages, which are the languages of Petri Nets, there are Context-free languages, which are not languages of Petri Nets. Such examples of Context-freе language we are noted the following:
(in particular,
). This fact illustrates the limitation of Petri Net as a tool, that generates the languages [1].
In Petri Nets is not possible to remember arbitrarily long sequence of arbitrary characters. In Petri Nets the sequence of limited length can be remembered (this is also possible in finite automata) [1].
However, Petri Nets do not have the “capacity of pushdown memory” which is necessary for the generation of Context-free languages. The interrelation of languages of Petri Nets with other classes of languages investigated Ven [1], this is shown in Figure 1 in the form of a diagram.
3. Results
We modeled 
language (star Klin) by CPN, in particular
.
The Figure 2 shows a Colored Petri Net, which generates the 
language that is, Colored Petri Net is a more powerful tool than the classical Petri Net. To understand types of data which are used in a figure, it is necessary to give a declaration.
In the figure introduced two positions of count of type and marked as first and second. In the figure, two transitions marked with the symbol a that are generating symbol a, and a transition marked with the symbol b, which generates the symbol b.
In the figure position of count of type remembers the number of transitions are fired and regulates, so the number of appearances a symbol b was equal to the number of appearances a symbol a.
In fact, when the marked with a transition is fired, generates the symbol a, if the marked with b transition is fired, generates the symbol b. To the transitions are attached logical expressions (guards):
, if the logical expression is true, then the transition is allowed, and if false, then the transition is not allowed. If the first position of count of type value of token is equal to one, the marked with a first transition is fired. The value of n must be fixed advance.
Let n = 2, then is fired marked with a the first transition, and ct = 2, then is fired marked with a the second transition, are generated by aa symbols, in this case second position of count of type value of token is equal to
Figure1. Interrelation of Petri nets and traditional languages (T-0—the General type of languages, CS—Contextsensitive languages, PNL—Petri nets languages, CF—Context-free languages, BCF—bonded Context-free languages, R—Regular languages).
Figure 2. Modeling 
language by Colored Petri Net.
Figure 3. Interrelation of Colored Petri Nets and traditional languages. CPNL (language of Colored Petri Net).
two: count= 2, and twice is fired marked with b the transition, are generated by bb, when the value of the first counter is equal to one, cycle will be repeated, etc.
Many properties of colored Petri nets, as logical expressions, types of markers, the expression of the arcs, etc., which are used to control the transition firing [3].
In Figure 2 Colored Petri Net is constructed for the given language, which supposes following interrelation of languages of Colored Petri Net with some of traditional languages classes (Figure 3).