A Petri net has a certain number of Places and Transitions. The state of a Petri net is defined by the sets of token residing in the different Places. A transition is enabled when all its Input-Places contain at least one token. The action performed by a transition is to remove a token from each Input-Place and add a token to each Output-Place. The semantics may be considered in the context of "interleaving semantics" or with concurrency for different transitions (in the latter case, each transition may take some time to execute).
Here is an exhaustive Web site on Petri nets. And here are some simple examples with simulations. For an overview, see also Wikipedia. Here is a nice tool set for Colored Petri nets.
The following is a skechy introduction using diagrams from the book: C. Girault and R. Valk, Petri Nets for Systems Engineering,
Springer Verlag, 2003
The example (a) below has two initial tokens; without the token in place R, the transition 3 and 4 will never fire.The token in place R may be considered to represent a resource that is required to perform transitions 3 and 4. Such a resource may be a tool, machine, or a person doing the job of these transitions.
The example (b) shows two transitions that are said to be in conflict. If there is only one token in each place, they cannot be executed both, but only one (a choice must be made). The example (c) shows two transitions that have a so-called free choice. If all choices in a net are of this type, the net is called a free-choice net.
The example (d) below shows how mutual exclusion can be modelled. There are two processes, on the left and on the right, and their critical sections are transitions 1 and 2, and 3 and 4, respectively. The single resource token in the middle assures that only one side can be active in its critical section at a time.
The example (e) shows how message passing can be modelled between a process on the left and a process on the right. A toekn in the place labelled m represents a message. Transition 1 "sends" a message, transition 2 "receives" a message. If one has different types of messages, one needs one place for each message type, since in pure Petri nets, tokens are not distinguishable. However, if one uses Colored Petri nets, the tokens are distinguishable by their value ("color"), and they may reside in the same place. However, Petri net places have no FIFO property. If that property is desired, one may use the so-called FIFO-nets, or model a queue explicitely in terms of Petri net places and transitions.
The following two examples use colored tokens. Each token has a value of a certain type, such as Integer, CharacterString, etc. It may also contain a value which is a tuplet. In these examples the value of a token passing through an input or output arc is written in "<" and ">". In most cases, variable names are used to represent values (e.g. <k, d> means the token has the value which is a tuplet consisting of k (which stands for key) and d (which stands for data) - so <k, d> is an element of a relation which has two attributes, key and data).
In a colored Petri net, a transition usually has a predicate which must be true. The predicate relates the values of incoming and outgoing tokens. The example (a) represents a net which counts the number of times the transition 3 is execution. The transition 1 puts a token into place c with value 0 (initialization). The transition 2 removes the token from place c, which means the counting stops and transition 3 cannot be executed any more. Transition 3 has a condition which assures that the new token put into place c has a value one unit larger than the token that was taken from that place (this assures correct counting).
In example (b), the place in the middle represents a database. Transition 1 enters tuplets into the database, transition 3 can be executed if the database contains a tuplet with the same key as provided by the token in the upper input place (the value k'). The content of the database is not changed. Transition 2, similarly selects a tuplet fitting with a given key, but the tuplet is removed from the database.
Final note: similar modeling approaches may be used when Activity Diagrams are used instead of Petri nets. Here is the same application modeled as Activity diagram, Use Case Map, and Petri net.
Created February 2008; last update: February 2, 2013