Ableitung (Informatik)

Als Ableitung wird in der theoretischen Informatik der Vorgang bezeichnet, ein Wort nach den Regeln einer formalen Grammatik zu erzeugen.

Unter einem Wort versteht man eine beliebige Zeichenkette, also eine endliche Folge von Symbolen. Eine formale Grammatik ist ein mathematisches Modell, das eine Menge solcher ableitbaren Wörter festlegt. Diese Menge nennt man eine formale Sprache. Das einmalige Ersetzen von einem Teilabschnitt einer Zeichenkette, gemäß einer der Regeln der formalen Grammatik, stellt einen Ableitungsschritt dar. Durch die formale Grammatik werden auch die Symbole festgelegt, aus denen ein Wort bestehen darf, und solche, die alleine in den Zwischenergebnissen der Ableitung eines Wortes auftreten dürfen. Zum Ableiten eines Wortes beginnt man mit einem besonderen Symbol, dem Startsymbol, und führt dann nacheinander Ableitungsschritte durch (bei Wahl geeigneter Regeln), bis schließlich das Wort erzeugt worden ist.

Anwendungsbereich

Darstellung eines Ableitungsbaums

Die Frage nach der Zugehörigkeit eines Wortes zu einer Sprache wird Wortproblem genannt. Ob ein Wort zur Sprache einer Grammatik gehört, wird darüber definiert, ob eine Ableitung des Wortes existiert. Eine Ableitung eines Wortes nach den Regeln einer Grammatik ist deshalb ein mathematischer Beweis dafür, dass das Wort zur Sprache der gegebenen Grammatik gehört.

Bei geeigneten Grammatiken (den kontextfreien) ergibt sich aus der Ableitung eines Wortes ein Ableitungsbaum. Zu einer Ableitung existiert in der Regel genau ein Ableitungsbaum. Gibt es aber zu einem Wort mehrere Ableitungen, die auch unterschiedliche Ableitungsbäume ergeben, ist die Grammatik mehrdeutig.

Der Syntaxanalyseteil („Parser“) eines Compilers analysiert den Quelltext eines Programms anhand der Grammatikregeln der verwendeten Programmiersprache. Dabei stellt er auch fest, ob das Programm ein Wort der betreffenden Programmiersprache ist, ob es also syntaktisch korrekt ist. Bei der Analyse des Quelltexts sucht der Parser indirekt nach einer Ableitung. Scheitert er dabei, weil das Programm einen Syntaxfehler enthält, ist nachgewiesen, dass zu dem Programm keine Ableitung existiert.

In der genetischen Programmierung verwendet man einem Ansatz zufolge zufällige Ableitungsbäume einer Grammatik, um Lösungen zu generieren.

Definitionen

Sei $G=\left(V,T,P,S\right)$ eine Chomsky-Grammatik. $T$ steht dabei für das endliche Alphabet der Terminale, also für Zeichen (der zu erzeugenden Sprache), die nicht weiter abgeleitet werden. $V$ steht für das gesamte Vokabular an Zeichen, das neben den Terminalen auch die Nonterminale oder Nichtterminalsymbole aus $N:=$ $V\setminus T$, also die Zeichen, die noch zu Terminalen umgewandelt werden müssen (und deshalb gelegentlich auch Variablen genannt werden). Das Startsymbol $S$ ist ein Nichtterminal. Ein Zeichen kann nicht gleichzeitig Terminal und Nichtterminal sein. Die Produktionsregeln $P$ beschreiben, in welcher Weise die Nichtterminale zu Terminale abgeleitet werden.

Manche Autoren bezeichnen alternativ das Quadrupel $(N,T,P,S)$ als Grammatik $G$ mit der Forderung, dass der Disjunktheit von Nonterminal- und die Terminalmenge: $N\cap T=\emptyset$; zum Teil werden auch anderen Bezeichnungen für die einzelnen Komponenten verwendet.

Satzform

Eine Satzform $x$ einer Grammatik $G$ ist eine Folge von Symbolen aus $N$ oder $T$: $x\in \left(N\cup T\right)^{*}=V^{*}$.

Ableitungsschritt

Ein Ableitungsschritt ist ein Teil einer Ableitung, der mit einer Produktionsregel ein $w$ nach einem $w'$ überführt. $w$ und $w'$ sind dabei Folgen aus Terminalen und Nichtterminalen. Eine Ableitungsregel $p=(\alpha ,\beta )$ wird formal notiert als $p=\alpha \rightarrow \beta$. Die zulässigen $\alpha$ und $\beta$ unterliegen dabei, je nach dem Typ der Grammatik, mehr oder weniger starken Einschränkungen.

Liegt ein Wort $w=w_{1}\alpha w_{2}\in V^{+}$ vor, so lässt sich die Produktionsregel $\alpha \rightarrow \beta \in P$ auf $w$ anwenden, mit dem resultierenden Wort $w'=w_{1}\beta w_{2}$. Man schreibt dann $w\rightsquigarrow w'$ (oder auch $w\Rightarrow _{G}w'$). Um anzugeben, welche Produktionsregel benutzt wurde, schreibt man auch $w\rightsquigarrow _{\alpha \rightarrow \beta }w'$. Formal ist die Relation $\rightsquigarrow$ auf der Menge aller Worte aus Terminalen und Nichtterminalen gegeben durch

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \rightsquigarrow\;:=\;\{(w \alpha w', w \beta w') | (\alpha,\beta)\in P \land w,w'\in V^*\}} .

Ableitungsstück

Ein Ableitungsstück ist eine endliche Folge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (w_0, \dotsc, w_n)} von Satzformen, worin jede folgende stets aus der unmittelbaren Vorgängerin durch einen Ableitungsschritt hervorgeht. Geschrieben kurz

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w_0 \rightsquigarrow_G w_1 \rightsquigarrow_G \dotsb \rightsquigarrow_G w_n}

Werden mehrere Regeln auf einmal angewendet, schreibt man Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w {\rightsquigarrow_G}^* w'} (in Analogie zur Kleeneschen Hülle, siehe: Relationen §Homogene Relationen). Formal ist die Relation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle {\rightsquigarrow_G}^*} als Vereinigung wie folgt darstellbar:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle {\rightsquigarrow_G}^* = \bigcup_{n \in \mathbb N_0} {\rightsquigarrow_G}^n}

Ableitung

Eine Ableitung ist ein Ableitungsstück, das mit dem Startsymbol beginnt und dessen letzte Satzform ein Wort ist. Eine Ableitung (in n Schritten) Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S {\rightsquigarrow_G}^n w_n} lässt sich also als Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S \rightsquigarrow w_1 \rightsquigarrow_G w_2 \rightsquigarrow_G \dotsb \rightsquigarrow_G w_n} notieren, wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w_n \in T^*} nur noch Terminalsymbole enthält. Nichtberücksichtigung der (endlichen) Zahl von Schritten führt zu Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S {\rightsquigarrow_G}^* w} , wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w_n \in T^*} aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S} ableitbar ist.

Erzeugte Sprache

Die von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} erzeugte Sprache Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L(G)} ist die Menge aller Worte über dem Zeichenalphabet Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle T} , die am Ende einer Ableitung stehen; man sagt auch, die ableitbar sind.

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L(G) := \{w \in T^* | S {\rightsquigarrow_G}^* w\} = \{w \in T^* | S \rightsquigarrow_G \cdots \rightsquigarrow_G w\}}

Im Allgemeinen sind auf eine Satzform mehrere verschiedene Produktionen anwendbar, und ein und dieselbe Produktion kann auch an verschiedenen Stellen anwendbar sein.

Beispiele

Sprache der Palindrome

Ein Ableitungsbaum für abcacba

Palindrome lassen sich durch eine kontextfreie Grammatik erzeugen. Wir beschränken uns im Beispiel auf ein Alphabet aus den drei Buchstaben Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c} .

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G_1 = \left(V, T, S, P\right)} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N := V \setminus T} und

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N = \{S\}}

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle T = \{a, b, c\}}

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P = \{ S\rightarrow aSa,\ S\rightarrow bSb,\ S\rightarrow cSc,\ S\rightarrow a,\ S\rightarrow b,\ S\rightarrow c,\ S\rightarrow \epsilon \}}

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \epsilon} steht für das leere Wort.

Mit dieser Grammatik lassen sich alle aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c} bestehenden Palindrome erzeugen. Eine Ableitung des Wortes Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle abcacba} lautet Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S \rightsquigarrow aSa \rightsquigarrow abSba \rightsquigarrow abcScba \rightsquigarrow abcacba} .

Sprache der positiven geraden Ganzzahlen

Auf eine formale Notation der Grammatik Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G_2} wurde an dieser Stelle verzichtet. Die Zahlen können beliebig viele führende Nullen haben.

Die Terminale sind die Ziffern von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 0} bis Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 9} (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle T = \{ 0, ... 9 \}} ), als Nonterminale dienen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S} (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N = \{ A, S \}} ), wobei letzteres gleichzeitig das Startsymbol ist: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle T = \{ 0, ... 9 \}, N = \{ A, S \}}

Die Produktionsregeln Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P} sind:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S \rightarrow A0 | A2 | A4 | A6 | A8} ,

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A \rightarrow A0 | A1 | A2 | A3 | A4 | A5 | A6 | A7 | A8 | A9 |\epsilon}

(Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X \rightarrow a | b |\dots} ist eine Kurzschreibweise für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X \rightarrow a, X \rightarrow b,\dots} )

Die Ableitung beginnt mit einer Regel, die auf der linken Seite das Startsymbol Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S} enthält. Die Ableitung beginnt beispielsweise mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S \rightsquigarrow A2} . Die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2} am Ende kann durch Regelanwendungen nicht entfernt werden, die entstehende Zahl ist also auf jeden Fall gerade. Das Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A} muss nun nach einer der Regeln mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A} auf der linken Seite weiter ersetzt werden. Eine mögliche Fortsetzung der Ableitung ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A2\Rightarrow A42} . Es können noch weitere Ziffern erzeugt werden; da am Ende der Ableitung aber alle Nichtterminale verschwunden sein müssen, muss irgendwann die Regel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A\rightarrow \epsilon} Anwendung finden. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \epsilon} ist das leere Wort, umgangssprachen kann man sagen, dass das Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A} durch nichts ersetzt wird. Die Beispielableitung wird also mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A42 \rightsquigarrow 42} abgeschlossen.

Mit den Produktionsregeln lässt sich jede beliebige positive, gerade Zahl erzeugen. Andere Zahlen lassen sich mit ihnen nicht erzeugen.

Sprache der Strichzahlen

Die Sprache der Strichzahlen wird etwa erzeugt von

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G_3 = \left(\{Z,i\}, \{i\}, \{Z \rightarrow i, Z \rightarrow i Z\}, Z \right)} ,

wobei mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i} der Ziffernstrich bezeichnet ist. Die Ableitung, die zur 5-Strichzahl führt, ist etwa:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Z \rightsquigarrow_{Z\rightarrow i Z} i Z \rightsquigarrow_{Z\rightarrow i Z} i i Z \rightsquigarrow_{Z\rightarrow i Z} i i i Z \rightsquigarrow_{Z\rightarrow i Z} i i i i Z \rightsquigarrow_{Z\rightarrow i} i i i i i}

Im Falle dieser Grammatik enthält jede Satzform keinmal oder genau einmal die Z, die in diesem Falle auch stets am Ende der Satzform steht. Es sind also alle Ableitungen Rechtsableitungen. Jedes Strichzahl hat mit dieser Grammatik genau eine mögliche Ableitung.

Dieselbe Sprache wird ebenfalls erzeugt von der Grammatik

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G_4 = \left(\{Z,i\}, \{i\}, \{Z \rightarrow i, Z \rightarrow Z Z\}, Z \right)} .

Das folgende ist damit eine Ableitung für die 3-Strichzahl:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Z \rightsquigarrow_{Z\rightarrow Z Z} Z Z \rightsquigarrow_{Z\rightarrow Z Z} Z Z Z \rightsquigarrow_{Z\rightarrow i} Z Z i \rightsquigarrow_{Z\rightarrow i} Z i i \rightsquigarrow_{Z\rightarrow i} i i i} .

Man beachte, im zweiten Schritt bleibt hierbei unklar, ob das rechte oder das linke Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Z} in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Z Z} durch ein weiteres Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Z Z} ersetzt wird; beidesmal entsteht zunächst Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Z Z Z} . Mit der Angabe, dass es sich um eine Rechtsableitung handle, wird die Ersetzungsstelle eindeutig. Dieselbe Eindeutigkeit wird erreicht, wenn man immer die genaue Stelle der Ersetzung, den sogenannten Henkel (englisch handle) mit angibt.

Parsen

Den umgekehrten Vorgang, bei dem ein Wort gegeben ist und eine Ableitung gesucht ist, nennt man auch parsen. Hierbei finden Automaten Anwendung, die überprüfen, ob das gegebene Wort aus den Ableitungsregeln entstanden sein kann. Von besonderer Bedeutung ist die Syntaxüberprüfung bei Programmiersprachen. Da es sich hierbei häufig um kontextfreie Sprachen handelt, ist ein Kellerautomat nötig.

Rechtsableitung

Eine Ableitung heißt Rechtsableitung (englisch rightmost derivation), wenn in jedem ihrer Einzelschritte immer das am weitesten rechts stehende Nichtterminalsymbol der Satzform gemäß einer Produktion ersetzt wird.

Beachte: Von Rechtsableitung spricht man nur, wenn eine kontextfreie Grammatik (Chomsky-Grammatik vom Typ 2) vorliegt; solche Grammatiken sind auch der in der Praxis der Informatik am häufigsten auftretende Sprachtyp. In diesem Fall hat jede Produktion die einfache Gestalt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A \rightarrow \alpha} , alle linken Seiten sind also einzelne Nichtterminalsymbole, die rechten bleiben beliebig. Der einzelne Ableitungsschritt ersetzt deshalb ein Vorkommnis eines Nichtterminalsymbols Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A} in der Ausgangs-Satzform durch eine der möglichen rechten Seiten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \alpha} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A\rightarrow \alpha \in P} .

Im Falle von Rechtsableitungen genügt die Angabe allein der Folge angewandter Produktionen, um den Gesamt-Ersetzungsvorgang (welche Ersetzungen an welchen Stellen?) und sein Ergebnis eindeutig zu beschreiben, was für beliebige Ableitungen nicht so ist, weil eine auftretende Satzform etwa Nichtterminalsymbole mehrfach enthalten kann.

Im Bereich des Compilerbaus sind Rechtsableitungen bedeutsam, weil für eine dort wichtige Sprachklasse, die LR(k)-Sprachen, eine effiziente Methode der Syntaxanalyse bekannt ist, der wesentlich dieser Begriff zugrunde liegt.

Linksableitung

Analog zur Rechtsableitung spricht man von einer Linksableitung (englisch leftmost derivation), wenn immer das am weitesten links stehende Nichtterminalsymbol ersetzt wird.

Linksableitungen spielen eine Rolle bei der Syntaxanalyse von LL(k)-Grammatiken, da aber die ihrer größeren Erzeugungsmächtigkeit wegen wichtigere Klasse der LR(k)-Grammatiken auf Rechtsableitungen beruht, insgesamt eine geringere. Diese scheinbare Asymmetrie ist eine Folge der Konvention, Eingabezeichenketten von links nach rechts zu lesen und zu verarbeiten.

Literatur

• Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman: Compilers – Principles, Techniques and Tools (= Addison-Wesley Series in Computer Science.) Addison-Wesley, Reading MA u. a. 1986, ISBN 0-201-10088-6, S. 196–197.
• Arto K. Salomaa: Formale Sprachen. Springer Verlag, Berlin u. a. 1978, ISBN 3-540-09030-4.
• Seppo Sippu, Eljas Soisalon-Soininen: Parsing Theory. 2 Bände. Springer Verlag, Berlin u. a. 1988, ISBN 3-540-13720-3 (Band 1), ISBN 3-540-51732-4 (Band 2), (EATCS Monographs on theoretical Computer Science 15 und 20).