Nebenläufige Automaten (Petri-Netze)

Ziel: Modellierung von Systemen mit verteiltem Zustand.

• Petri-Netz P = (S, T, F) mit F⊆S×T∪T×S

• Vorbereich einer Transition: vor(t) = {s | (s, t)∈F}, Nachbereich nach(t) = …
• Markierung von P: ist Funktion m : S→$\mathbb {N}$
• eine Transition t schaltet:

  wenn alle Stellen im Vorbereich von t markiert sind,
  dann je eine Marke aus Vorbereich einziehen,
  und je eine Marke im Nachbereich austeilen

P definiert Zustandsübergangssyst. auf $\mathbb {N}$^S mit Alphabet T.

In Spezialfällen ist die erreichbare Zustandsmenge endlich (und damit die Sprache regulär)