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.

Im einfachsten Fall ist eine Transitionsrelation Δ {\displaystyle \Delta } eine Menge aus Zustandspaaren, wobei die Zustandsmenge hier als Z {\displaystyle Z} bezeichnet wird.

Δ ⊆ Z × Z {\displaystyle \Delta \subseteq Z\times Z}

Das Paar ( z , z ′ ) ∈ Δ {\displaystyle (z,z')\in \Delta } bedeutet dann, dass ein Übergang von z {\displaystyle z} nach z ′ {\displaystyle z'} möglich ist. Übergänge zwischen Konfigurationen aus K {\displaystyle K} sind entsprechend definiert:

Δ K ⊆ K × K {\displaystyle \Delta _{K}\subseteq K\times K}

Ist der Zustandsübergang von einem Eingabesymbol aus dem Alphabet Σ {\displaystyle \Sigma } abhängig, ist die Definition wie folgt:

Δ ⊆ Z × Σ × Z {\displaystyle \Delta \subseteq Z\times \Sigma \times Z}

Das Tupel ( z , a , z ′ ) ∈ Δ {\displaystyle (z,a,z')\in \Delta } bedeutet, dass vom Zustand z {\displaystyle z} durch das Symbol a {\displaystyle a} ein Wechsel in den Zustand z ′ {\displaystyle z'} möglich ist.

Die Transitionsrelation wird häufig in Infixnotation als Ableitungspfeil geschrieben: z → Δ z ′ {\displaystyle z\rightarrow _{\Delta }z'} .

Eine Transitionsrelation Δ {\displaystyle \Delta } lässt sich auch als Transitionsfunktion δ {\displaystyle \delta } 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 Multifunktionen mit Bild = Urbild (wobei δ = Δ ~ {\displaystyle \delta ={\tilde {\Delta }}} ).

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

δ : Z → P ( Z ) {\displaystyle \delta \colon Z\to {\mathcal {P}}(Z)}

Der Transitionsrelation Δ 1 = { ( z 0 , z 1 ) , ( z 0 , z 2 ) } {\displaystyle \Delta _{1}=\{(z_{0},z_{1}),(z_{0},z_{2})\}} entspricht beispielsweise die Transitionsfunktion

δ 1 {\displaystyle \delta _{1}} mit δ 1 ( z 0 ) = { z 1 , z 2 } {\displaystyle \delta _{1}(z_{0})=\{z_{1},z_{2}\}} .

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

δ : Z → Z {\displaystyle \delta \colon Z\to Z}

Hängt der Übergang von einem Symbol aus Σ {\displaystyle \Sigma } ab, ist der Definitionsbereich der Funktion die Menge der Paare aus Zustand und Eingabesymbol.

δ : Z × Σ → P ( Z ) {\displaystyle \delta \colon Z\times \Sigma \to {\mathcal {P}}(Z)} .

Die Transitionsrelation einer formalen Grammatik G (bezeichnet durch den Operator ⇝ G {\displaystyle \rightsquigarrow _{G}} ) 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 G = ( V , Σ , P , S ) {\displaystyle G=\left(V,\Sigma ,P,S\right)} ist dann die Transitionsrelation ⇝ G {\displaystyle \rightsquigarrow _{G}} folgendermaßen definiert:

⇝ G ⊆ ( V ∗ ∖ Σ ∗ ) × V ∗ {\displaystyle \rightsquigarrow _{G}\,\subseteq (V^{*}\setminus \Sigma ^{*})\times V^{*}} , wobei u ⇝ G v {\displaystyle u\rightsquigarrow _{G}v} , falls u = x y z {\displaystyle u=xyz} , v = x y ′ z {\displaystyle v=xy'z} , y → y ′ ∈ P {\displaystyle y\rightarrow y'\in P} mit x , z ∈ V ∗ {\displaystyle x,z\in V^{*}} .

Falls klar ist, um welche Grammatik G {\displaystyle G} es sich handelt, schreibt man oft einfach u ⇝ v {\displaystyle u\rightsquigarrow v} .

• 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).