Wichtiger Hinweis zum Inhalt des Online-LexikonsBei den auf dieser Seite aufgeführten Texten/Artikeln/Inhalten handelt es sich ausschließlich um fremde Inhalte, die sich die Aschendorff Verlag GmbH & Co. KG ausdrücklich nicht zu Eigen macht. Diese fremden Inhalte, die keiner regelmäßigen Überprüfung unterliegen, sind ausnahmslos solche der freien Enzyklopädie Wikipedia, für die keinerlei Verantwortung übernommen wird.

---

Lizenzbestimmungen Der Text/Artikel/Inhalt auf dieser Seite innerhalb der Rubrik "Online Lexikon" basiert, soweit nicht anders angegeben, auf dem Artikel Ableitungsrelation aus der freien Enzyklopädie Wikipedia. Die Inhalte stehen unter der GNU Lizenz für freie Dokumentation. Eine Liste der Autoren ist dort abrufbar.

Transitionsrelation

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.

Definition

Formal lässt sich eine Transitionsrelation T als Abbildung beschreiben: $T:\; z,\; x\_1,\; ...,\; x\_n\; \backslash rightarrow\; z\text{'}$. Dem entsprechend kann sie auch als Menge von Tupeln der Form $(z,x\_1,...,x\_n,z\text{'})$ betrachtet werden, die eine Relation definiert, also $T\; \backslash subset\; Z\; \backslash times\; X\_1\; \backslash times\; ...\; \backslash times\; X\_n\; \backslash 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\; \backslash Rightarrow\_T\; z\text{'}$.

Formale Sprachen

Die Transitionsrelation einer formalen_Grammatik G (bezeichnet durch den Operator $\backslash 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.
Für eine formale Grammatik $G\; =\; \backslash left(\; N,\; \backslash Sigma,\; P,\; S\; \backslash right)$ ist dann die Transitionsrelation $\backslash Rightarrow\_G$ folgendermaßen definiert:

$\backslash Rightarrow\_G\; \backslash ,\; \backslash subseteq\; \backslash left(\; N\; \backslash cup\; \backslash Sigma\; \backslash right)^+\; \backslash times\; \backslash left(\; N\; \backslash cup\; \backslash Sigma\; \backslash right)^*$, wobei $u\; \backslash Rightarrow\_G\; v$, falls $u\; =\; xyz$, $v\; =\; xy\text{'}z$, $y\; \backslash rightarrow\; y\text{'}\; \backslash in\; P$ mit $x,\; z\; \backslash in\; \backslash left(\; N\; \backslash cup\; \backslash Sigma\; \backslash right)^*$.

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

Siehe auch

• (Grammatik)], Ableitung (Informatik)

       VIDEO-NEWS UND ANGEBOTE