Ableitungsrelation

Eine Transitionsrelation ist in der Informatik eine Abbildung, die einen Zustand z auf einen Folgezustand z' abbildet. Die Transitionsrelation bildet zusammen mit einer Zustandsmenge ein Transitionssystem, das das Verhalten eines Automaten beschreibt.

Neben dem Ausgangszustand kann die Abbildung (möglicherweise) beliebige weitere Parameter haben. Meist gibt es neben dem Ausgangszustand genau einen weiteren Parameter, nämlich ein Eingabezeichen, das in diesem Zustand gelesen wurde.

Definition

Formal lässt sich eine Transitionsrelation T als Abbildung beschreiben: $T: z, x_1, ..., x_n \rightarrow z'$. Dem entsprechend kann sie auch als Menge von Tupeln der Form (z,x₁,...,x_n,z') betrachtet werden, die eine Relation definiert, also $T \subset Z \times X_1 \times ... \times X_n \times Z$, wobei Z die (möglicherweise unendliche) Menge der möglichen Zustände ist.

Die Transitionsrelation wird häufig in Infixnotation als Ableitungspfeil geschrieben: $z \Rightarrow_T z'$.

Formale Sprachen

Die Transitionsrelation einer formalen Grammatik G (bezeichnet durch den Operator $\Rightarrow_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.

Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung.

Für eine formale Grammatik $G = \left( N, \Sigma, P, S \right)$ ist dann die Transitionsrelation $\Rightarrow_G$ folgendermaßen definiert:

$\Rightarrow_G \, \subseteq \left( N \cup \Sigma \right)^+ \times \left( N \cup \Sigma \right)^*$, wobei $u \Rightarrow_G v$, falls u = xyz, v = xy'z, $y \rightarrow y' \in P$ mit $x, z \in \left( N \cup \Sigma \right)^*$.

Falls klar ist, um welche Grammatik G es sich handelt, schreibt man oft einfach $u \Rightarrow v$.