Transitionsrelation - LinkFang.de





Transitionsrelation


Eine Transitionsrelation (auch Übergangsrelation) ist in der Informatik eine Relation, die mögliche Übergänge beschreibt. In Transitionssystemen und bei Automaten gibt eine Transitionsrelation an, welche Zustandswechsel möglich sind. Man spricht dann auch von einer Zustandsübergangsrelation. Eine Transitionsrelation ist aber nicht auf Zustandswechsel beschränkt. Sie kann auch Übergänge zwischen Konfigurationen beschreiben. Üblicherweise werden Relationen über Konfigurationen aber aus Zustandsübergangsrelationen abgeleitet. Es lassen sich damit jedoch auch operationelle Semantiken definieren.

Befinden sich zwei Zustände in Relation, so ist ein direkter Wechsel von einem Zustand in den anderen möglich, andernfalls nicht. Es ist auch möglich, dass die Relation aus weiteren Parametern besteht, etwa einem Eingabesymbol, von dem der Zustandswechsel abhängt. Für Zustandsübergänge nach beliebig langen Eingaben verwendet man die reflexive und transitive Hülle einer Transitionsrelation.

Transitionen werden auch durch Funktionen definiert. Man spricht dann von Transitionsfunktionen oder Übergangsfunktionen.

Definition

Im einfachsten Fall ist eine Transitionsrelation [math]\Delta[/math] eine Menge aus Zustandspaaren, wobei die Zustandsmenge hier als [math]Z[/math] bezeichnet wird.

[math]\Delta \subseteq Z \times Z[/math]

Das Paar [math](z,z')\in \Delta[/math] bedeutet dann, dass ein Übergang von [math]z[/math] nach [math]z'[/math] möglich ist. Übergänge zwischen Konfigurationen aus [math]K[/math] sind entsprechend definiert:

[math]\Delta_K \subseteq K \times K[/math]

Ist der Zustandsübergang von einem Eingabesymbol aus dem Alphabet [math]\Sigma[/math] abhängig, ist die Definition wie folgt:

[math]\Delta \subseteq Z \times \Sigma \times Z[/math]

Das Tupel [math](z,a,z') \in \Delta[/math] bedeutet, dass vom Zustand [math]z[/math] durch das Symbol [math]a[/math] ein Wechsel in den Zustand [math]z'[/math] möglich ist.

Die Transitionsrelation wird häufig in Infixnotation als Ableitungspfeil geschrieben: [math]z \rightarrow_\Delta z'[/math].

Transitionsfunktion

Eine Transitionsrelation lässt sich auch als Transitionsfunktion darstellen. Statt einen Zustand mit seinen möglichen Nachfolgezuständen in Relation zu setzen, bildet die Transitionsfunktion einen Zustand auf die Menge der möglichen Nachfolgezustände ab.

Die Definition ist daher im einfachsten Fall eine Funktion, die von der Zustandsmenge in ihre Potenzmenge abbildet.

[math]\delta : Z \to \mathcal{P}(Z)[/math]

Der Transitionsrelation [math]\Delta_1 = \{(z_0,z_1),(z_0,z_2)\}[/math] entspricht beispielsweise die Transitionsfunktion [math]\delta_1[/math] mit [math]\delta_1(z_0)=\{z_1,z_2\}[/math].

Ist Nichtdeterminismus ausgeschlossen, gibt es also zu jedem Zustand einen eindeutigen Nachfolgezustand, kann auch von Zuständen auf Zustände abgebildet werden:

[math]\delta : Z \to Z[/math]

Hängt der Übergang von einem Symbol aus [math]\Sigma[/math] ab, ist der Definitionsbereich der Funktion die Menge der Paare aus Zustand und Eingabesymbol.

[math]\delta : Z \times \Sigma \to \mathcal{P}(Z)[/math].

Formale Sprachen

Die Transitionsrelation einer formalen Grammatik G (bezeichnet durch den Operator [math]\rightsquigarrow_G[/math]) ist eine Relation, die besagt, dass sich das Wort rechts des Operators unmittelbar, also durch eine einzelne Produktion, aus dem Wort links des Operators ableiten lässt.

Für eine formale Grammatik [math]G = \left( V, \Sigma, P, S\right)[/math] ist dann die Transitionsrelation [math]\rightsquigarrow_G[/math] folgendermaßen definiert:

[math]\rightsquigarrow_G \, \subseteq (V^*\setminus\Sigma^*)\times V^*[/math], wobei [math]u \rightsquigarrow_G v[/math], falls [math]u = xyz[/math], [math]v = xy'z[/math], [math]y \rightarrow y' \in P[/math] mit [math]x, z \in V^*[/math].

Falls klar ist, um welche Grammatik [math]G[/math] es sich handelt, schreibt man oft einfach [math]u \rightsquigarrow v[/math].

Literatur

  • Katrin Erk, Lutz Priese: Theoretische Informatik: eine umfassende Einführung. 2., erw. Auflage. Springer-Verlag, 2002, ISBN 3-540-42624-8, S. 64 ff.
  • John C. Reynolds: Theories of Programming Languages. Cambridge University Press, 2009, ISBN 0-521-10697-4, S. 126 (eingeschränkte Vorschau in der Google-Buchsuche).

Kategorien: Theorie formaler Sprachen | Automatentheorie

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Transitionsrelation (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.