Linksableitung

Eine Rechtsableitung ist nach einer formalen Grammatik eine Ableitung eines Wortes w₀ in w_n, bei der in jedem Ableitungsschritt von w_i in w_{i + 1} ($i \in \mathbb{N}_0$ und i < n) stets das rechteste Nichtterminalsymbol von w_i ersetzt wird. Eine Linksableitung ist analog definiert, wobei hier in jedem Ableitungschritt das linkeste nichtterminale Symbol ersetzt wird.

Ein Rechtsableitungsschritt wird formal definiert durch

$\alpha \delta A\gamma w \Rightarrow_r \alpha \beta w$

und ein Linksableitungsschritt durch

$w \delta A\gamma\alpha \Rightarrow_l w \beta\alpha$

bei dem die Regel $\delta A\gamma \rightarrow \beta$ angewandt wurde. Dabei bedeuten:

• w ist ein Wort, welches nur aus Terminalsymbolen besteht.
• A ist ein Nichtterminalsymbol.
• α,β,γ und δ sind Wörter, die aus Terminal- und Nichtterminalsymbolen bestehen.

Bei kontextfreien Grammatiken ist δ und γ stets das leere Wort ε. Wenn in einer formalen Grammatik zu einem beliebigen Wort mehrere verschiedene Rechts- bzw. Linksableitungen existieren, heißt diese Grammatik mehrdeutig.

Beispiel

Es sei G = (N,T,R,S) eine Grammatik mit den Nichtterminalsymbolen N = {A,B,S}, den Terminalsymbolen T = {x,y}, dem Startsymbol S und den Produktionsregeln:

$\begin{align}\\ S &amp;amp;\rightarrow AA\\ AB &amp;amp;\rightarrow \mathrm x\\ A &amp;amp;\rightarrow B\\ B &amp;amp;\rightarrow \mathrm y \end{align}$

Dann ist die folgende Ableitung von S in yy eine Linksableitung:

$S\Rightarrow_l AA \Rightarrow_l BA \Rightarrow_l \mathrm yA \Rightarrow_l \mathrm yB \Rightarrow_l \mathrm y\mathrm y$

und die folgende Ableitung von S in x eine Rechtsableitung:

$S\Rightarrow_r AA \Rightarrow_r AB \Rightarrow_r \mathrm x$

Siehe auch

• Rechtsreduktion
• Inhärent mehrdeutige Sprache
• Syntaxbaum