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,x1,...,xn,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.


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Formale Systeme — Die Artikel Formale Sprache, Formales System, Formales System (Logik) und Kalkül überschneiden sich thematisch. Hilf mit, die Artikel besser voneinander abzugrenzen oder zu vereinigen. Beteilige dich dazu an der Diskussion über diese… …   Deutsch Wikipedia

  • Formales System — Ein formales System ist ein System von Symbolketten und Regeln. Die Regeln sind Vorschriften für die Umwandlung einer Symbolkette in eine andere, also Produktionen einer formalen Grammatik. Die Anwendung der Regeln kann dabei ohne Kenntnis der… …   Deutsch Wikipedia

  • Ableitung (Logik) — Unter Ableitung oder Herleitung, auch Deduktion, versteht man in der Logik die Gewinnung von Sätzen (den Konklusionen) aus anderen Sätzen (den Prämissen) in einem formalen Kalkül unter Verwendung der im Kalkül zugelassenen Schlussregeln.… …   Deutsch Wikipedia

  • Semi-Thue System — (oder auch Umformungssystem) ist in der Theoretischen Informatik ein Regelsystem zur Manipulation von Zeichenketten, also eine formale Grammatik. Motiviert durch David Hilberts Vortrag im Jahre 1900 und den Ausführungen über eine logische… …   Deutsch Wikipedia

  • Semi Thue System — (oder auch Umformungssystem) ist in der Theoretischen Informatik ein Regelsystem zur Manipulation von Zeichenketten, also eine formale Grammatik. Motiviert durch David Hilberts Vortrag im Jahre 1900 und den Ausführungen über eine logische… …   Deutsch Wikipedia

  • Thue-System — Semi Thue System (oder auch Umformungssystem) ist in der Theoretischen Informatik ein Regelsystem zur Manipulation von Zeichenketten, also eine formale Grammatik. Motiviert durch David Hilberts Vortrag im Jahre 1900 und den Ausführungen über eine …   Deutsch Wikipedia

  • Umformungssystem — Semi Thue System (oder auch Umformungssystem) ist in der Theoretischen Informatik ein Regelsystem zur Manipulation von Zeichenketten, also eine formale Grammatik. Motiviert durch David Hilberts Vortrag im Jahre 1900 und den Ausführungen über eine …   Deutsch Wikipedia

  • Begriffsschrift — Das Titelblatt der Begriffsschrift Die Begriffsschrift ist ein schmales, nur etwa achtzig Seiten umfassendes Buch des Jenaer Mathematikers und Philosophen Gottlob Frege zur Logik. Es wurde 1879 mit dem Untertitel „Eine der arithmetischen… …   Deutsch Wikipedia

  • Begriffsschriftnotation — Das Titelblatt der Begriffsschrift Die Begriffsschrift ist ein schmales, weniger als hundert Seiten umfassendes Buch des Jenaer Mathematikers und Philosophen Gottlob Frege zur Logik. Es wurde 1879 mit dem Untertitel „Eine der arithmetischen… …   Deutsch Wikipedia

  • Chomsky-Hierarchie — Chomsky Hierarchie, gelegentlich Chomsky–Schützenberger Hierarchie (benannt nach dem Linguisten Noam Chomsky und dem Mathematiker Marcel Schützenberger), ist ein Begriff aus der Theoretischen Informatik. Sie ist eine Hierarchie von Klassen… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”