Quelltext der Seite Transitionsrelation

Eine '''Transitionsrelation''' (auch ''Übergangsrelation'') ist in der [[Informatik]] eine [[Relation (Mathematik)|Relation]], die mögliche Übergänge beschreibt. In [[Transitionssystem]]en und bei [[Automat (Informatik)|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 Semantik]]en 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 [[Transitive Hülle (Relation)|reflexive und transitive Hülle]] einer Transitionsrelation.

Transitionen werden auch durch [[Funktion (Mathematik)|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 (Informatik)|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 <math>\Delta</math> lässt sich auch als Transitionsfunktion <math>\delta</math> 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. Es handelt sich dabei um [[Funktion (Mathematik)#Multifunktionen|Multifunktionen]] mit Bild = Urbild (wobei <math>\delta = \tilde \Delta</math>).

Die Definition ist daher im einfachsten Fall eine Funktion, die von der Zustandsmenge in ihre [[Potenzmenge]] abbildet.
:<math>\delta \colon 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 \colon 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 \colon Z \times \Sigma \to \mathcal{P}(Z)</math>.

== Formale Sprachen ==
Die Transitionsrelation einer [[Formale Grammatik|formalen Grammatik]] <span style="font-family:monospace;">G</span> (bezeichnet durch den [[Operator (Mathematik)|Operator]] <math>\rightsquigarrow_G</math>) ist eine [[Relation (Mathematik)|Relation]], die besagt, dass sich das [[Wort (Theoretische Informatik)|Wort]] rechts des Operators unmittelbar, also durch eine einzelne [[Produktionsregel|Produktion]], aus dem Wort links des Operators [[Ableitung (Informatik)|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 ==
* {{Literatur |Autor=Katrin Erk, Lutz Priese |Titel=Theoretische Informatik: eine umfassende Einführung |Auflage=2., erw. |Verlag=Springer-Verlag |Datum=2002 |ISBN=3-540-42624-8 |Seiten=64 ff.}}
* {{Literatur |Autor=John C. Reynolds |Titel=Theories of Programming Languages |Verlag=Cambridge University Press |Datum=2009 |ISBN=0-521-10697-4 |Seiten=126 |Online={{Google Buch|BuchID=2OwlTC4SOccC|Seite=126|Hervorhebung=transition relation}}}}

[[Kategorie:Automatentheorie]]
[[Kategorie:Theorie formaler Sprachen]]