erweiterte Ableitung
Einfache Sprache
Def. erweiterte Ableitung
Sei $\mathcal G = (V,T,S,P)$ eine Kontextfreie Grammatik. Wenn durch wiederholtes Anwenden von Ableitungen eine Zeichenkette $\beta\in\Sigma^*$ aus einer anderen Zeichenkette $\alpha\in\Sigma^*$ erhalten werden kann schreiben wir
$$\alpha\overset{*}{\underset{\mathcal G}\Rightarrow}\beta\;,$$bzw. $\alpha\overset{*}\Rightarrow\beta$ falls $\mathcal G$ aus dem Kontext klar ist.
Beweis: induktiv über die Anzahl der Ableitungsschritte. Es sei eine Kontextfreie Grammatik $\mathcal G$ gegeben.
IA: Es ist offensichtlich, dass jede Zeichenkette $\alpha\in\Sigma^*$ sich, in Null Ableitungsschritten, selbst ableitet. Also $\alpha\overset{*}\Rightarrow\alpha\;.$
IS: Sei $\alpha,\beta,\gamma\in\Sigma^*$. Dann folgt aus $\alpha\overset{*}\Rightarrow\beta$ und $\beta\Rightarrow\gamma$, dass $\alpha\overset{*}\Rightarrow\gamma$. Also $\alpha$ kann zu $\beta$ in 0 oder mehr Schritten abgeleitet werden und es braucht eine weitere Ableitung von $\beta$ zu $\gamma$.
Alternative können wir uns $\alpha\overset{*}\Rightarrow\beta$ als eine Folge von Zeichenketten $\gamma_1,\ldots,\gamma_n$ mit $y_i\in\Sigma^*$ für alle $i\in[1,n]$ vorstellen so, dass
- $\alpha =\gamma_1$,
- $\beta = \gamma_n$ und
- $\forall i\in[1,n-1]:\gamma_i\Rightarrow\gamma_{i+1}$ gilt.
Beispiel
Das Beispiel hier aber mit erweiterten Ableitung. Gegeben die Kontextfreie Grammatik $\mathcal G$ definiert durch die Produktionsregeln $E\to I\;|\; E+E\;|\;E*E\;|\;(E)$ und $I\to a\;|\;b\;|\; I0\;|\;I1\;|\;\varepsilon$. Dann ergibt sich durch erweiterte Ableitung das Wort $a*(q+b00)$ wie folgt:
$$E \overset{*}\Rightarrow a*(a*+b00)$$
Leftmost und Rightmost Ableitung
Ein $lm$ oder ein $rm$ unter dem Ableitungspfeil bedeutet, dass immer die Variable ganz links bzw. ganz rechts ersetzt werden muss.