Transitionssystem

Ein Transitionssystem (engl. labelled transition system) beschreibt in der Automatentheorie die möglichen Zustände eines Automaten (oder eines Petri-Netzes oder eines anderen Systems) und die möglichen Übergänge zwischen diesen Zuständen.

Ein Transitionssystem kann verwendet werden, um bestimmte Eigenschaften eines Automaten (bzw. eines zustandsbasierten Systems) zu zeigen, insbesondere die Terminiertheit. Aus disem Grund wird es zur Verifikation der Korrektheit von Algorithmen eingesetzt. Auch zum Beweis der Verklemmungsfreiheit von verteilten Systemen kann dieses Konstrukt angewendet werden, insbesondere im Zusammenhang mit Petri-Netzen.

Formale Definition

Formal wird das Transitionssystem beschrieben durch ein Quadrupel $TS=(S,S_{0},A,T)$, wobei

• $S$ ist eine Menge von Zuständen.
• $S_{0}\subseteq S$ ist die Menge der Startzustände.
• $A$ ist ein endliches Alphabet wobei $S\cap A=\emptyset$. Die Elemente von A heißen Markierungen (engl. label) von TS.
• $T\subseteq S\times A\times S$ ist die Transitionsrelation von TS: es bestimmt für jeden Zustand und jedes Eingabezeichen, welcher Zustand folgt.

Das Transaktionssystem entspricht also einem endlichen Automaten, nur dass die Zustandsmenge nicht endlich sein muss und die Transitionsrelation daher beliebig komplex sein kann. Schon diese scheinbar kleinen Erweiterungen führen dazu, dass Transitionssysteme im Allgemeinen turingmächtig sind.

Eigenschaften

Ein Transitionssystem TS heißt endlich, falls S (die Menge Zustände) endlich ist. Ein endliches Transitionssystem ist ein endlicher Automat. Solche Transitionssysteme können als Transitionsdiagramm dargestellt werden: Es bildet im Allgemeinen einen gerichteten zyklischen Graphen mit benannten Kanten.

Ein Transitionssystem TS heißt deterministisch, wenn die folgenden beiden Bedingungen erfüllt sind:

• $S_{0}$ enthält genau ein Element.
• Wenn $(z_{0},a,z_{1})\in T$, dann folgt für alle $(w_{0},b,w_{1})\in T$ mit $w_{0}=z_{0}$ und $b=a$ auch $w_{1}=z_{1}$.

In jedem Zustand ist also für jedes Eingabezeichen eindeutig festgelegt, was der nächte Zustand sein muss.

Beispiele

Ampel

Eine Ampel läßt sich als Transitionssystem verstehen. Eine Ampel besitzt die fünf Zustände $\{rot,rot-gelb,gruen,gelb,aus\}$. Im Normalbetrieb wechselt die Ampel ihre Zustände in folgender Reihenfolge: $rot\ {\overrightarrow {a}}\ rot-gelb\ {\overrightarrow {a}}\ gruen\ {\overrightarrow {a}}\ gelb\ {\overrightarrow {a}}\ rot$. Außerdem besitzt eine Ampel einen Nachtbetrieb:$gelb\ {\overrightarrow {b}}\ aus\ {\overrightarrow {b}}\ gelb$. Die Beschreibung dieser beiden Zyklen als Zustandsänderung nennt man Transitionssystem.

Deterministischer endlicher Automat

Der oben abgebildete Graph ist ein DEA mit den vier Zuständen $S_{0}$, $S_{1}$, $S_{2}$ und $S_{3}$. $S_{3}$ ist ein Endzustand. Das Alphabet besteht aus den beiden Buchstaben $a$ und $b$. Andere Buchstaben akzeptiert der Automat nicht. Das einzige Wort, das der oben abgebildete DEA akzeptiert ist $aba$.

Literatur

• John E. Hopcroft u. Jeffrey D. Ullman, Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, ISBN 3-89319-181-X
• Sander/Stucky/Herschel, Automaten, Sprachen, Berechenbarkeit, ISBN 3-519-02937-5