Ableitung mit Produktionsregeln

Einfache Sprache

Die Idee der Ableitung mit Produktionsregeln oder kurz Ableitung ist, ausgehend vom Startsymbol Produktionsregeln auf die Variablen in der Zeichenkette anzuwenden. Es werden also schrittweise Variablen mit Hilfe der entsprechenden Produktionsregeln ersetzt.

Def. Ableitung mit Produktionsregeln

Sei $\mathcal G = (V,T,S,P)$ eine Kontextfreie Grammatik. Sei $\alpha A\beta\in\Sigma^*$ mit $A\in V$, also $A$ ist ein Variable. Sei $A\to\gamma$ eine Produktionsregel in $P$. Dann kann $\alpha\gamma\beta$ aus $\alpha A\beta$ abgeleitet werden. Wir schreiben in solch einem Fall

$$\alpha A\beta\underset{\mathcal G}\Rightarrow \alpha\gamma\beta\;.$$

Falls $\mathcal G$ aus dem Kontext klar ist schreiben wir $\alpha A\beta\Rightarrow \alpha\gamma\beta$

Beispiel

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 Ableitung das Wort $a*(q+b00)$ aus folgenden Ableitungsschritten:

$$\begin{align}E &\Rightarrow E*E\\&\Rightarrow I*E\\&\Rightarrow a*E\\&\Rightarrow a*(E)\\&\Rightarrow a*(E+E)\\&\Rightarrow a*(I+E)\\&\Rightarrow a*(a + E)\\&\Rightarrow a*(a*+I0)\\&\Rightarrow a*(a*+I00)\\&\Rightarrow a*(a*+b00)\end{align}$$

Eine Erweiterung dieser Idee ist die erweiterte Ableitung.