-
Zur Startseite
Zum Editor

Zum Tutorial

PetriEdiSim

Tutorial zum Thema "Petri-Netze"
1.   Automaten (Grundlage für Petri-Netze)



   Nächstes Kapitel

1.   Automaten (Grundlage für Petri-Netze)

Um den Einstieg in die Theorie der Petri-Netze zu erleichtern, sind in diesem Kapitel die grundlegenden Konzepte von Automaten nochmal kurz zusammengefaßt. Automaten können als Grundlage für das Verständnis von Petri-Netzen verwendet werden. Die eigentlichen Petri-Netze werden hierauf aufbauend im nächsten Kapitel beschrieben. Sie sind eine Erweiterung von Automaten.

Als Einführung wird mit einigen Begriffen angefangen, die für die Definition von Automaten benötigt werden.


Comm sei eine unendliche Menge von Kommunikationen (externe Aktionen)
Comm ist ein Element für interne Aktionen
Act = Comm { } sei eine Menge von Aktionen


Als Kommunikationsalphabet oder kurz Alphabet wird hier eine endliche Teilmenge von Comm bezeichnet.
A , B sind Alphabete.
Jeder Prozeß hat ein Kommunikationsalphabet das mit ihm verbunden ist. Dieses Alphabet beschreibt die Schnittstelle mit der der Prozeß mit dem Anwender oder mit anderen Prozessen kommuniziert.
Im folgenden wird eine Definition von einem klassischen Automaten gegeben.


Definition :
Ein Automat ist eine Struktur
A = ( A, St, ->, q0)      wobei
  • A ist ein Alphabet
  • St  ist eine (mögl. unendliche) Menge von Zuständen
  • -> St × (A { }) × St ) ist die Schrittrelation
  • q0 ist der Anfangszustand

Die Zustände p , q und r sind Elemente der Menge St.
Ein Element  (p, u, q ) -> heißt Transition (mit der Aktion u als Label) und wird üblicherweise wie folgt geschrieben :

p q.

In der Theorie der Automaten entspricht die Menge A dem Eingabealphabet. Die internen Aktionen sind für den Anwender nach außen hin nicht sichtbar.

Jeder Automat A = ( A, St, ->, q0) besitzt eine graphische Darstellung die oft einfacher zu verstehen ist. Hierzu wird ein Rechteck gezeichnet, das in zwei Bereiche aufgeteilt ist. Im oberen Teil wird das Alphabet A beschrieben und im unteren Teil des Rechtecks steht das Zustandsdiagramm. Das Zustandsdiagramm ist ein Graph deren Kanten mit den Aktionen beschriftet sind. Dieser Graph repräsentiert die verbleibenden Komponenten St, -> und q0 des Automaten. Die Wurzel des Graphen wird mit einem eingehenden Pfeil gekennzeichnet.



Graphische Darstellung eines Automaten


Beispiel :
Alphabet




Zustandsdiagramm



Dieser Automat beschreibt einen Prozeß mit einer Kommunikationsschnittstelle bestehend aus a, b und c. Das Zustandsdiagramm zeigt, daß der Prozeß zu Beginn nur in der Lage ist, die Kommunikationen a oder b auszuführen und im Anschluß erst c (oder gar nichts mehr). Ob nun a oder b zuerst ausgeführt wird, ist die Wahl des Anwenders.


Wie gut sind Automaten als Prozeßmodell ?

+     sequentielle Abläufe
+     Nichtdeterminismus
-     Parallelität geht verloren



Im nächsten Kapitel werden die Grundlagen dieses Abschnitts verwendet um die Erweiterung von Automaten, die Petri-Netze, einzuführen.



  Nächstes Kapitel


© Copyright Oktober 1997 by Petra Hornstein