Transitionsrelation

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

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, dass 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.

[Bearbeiten] 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 1,..., 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'$ .

[Bearbeiten] 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 bitte 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 = x y z$ , $v = x y' z$ , $y \rightarrow y' \in P$ mit $x, z \in \left( N \cup \Sigma \right)^*$ .