Rechts/Links-Ableitungen

Def: eine Ableitung w₀$\to_{G}^{}$w₁$\to$... heißt Rechts- (bzw. Links-)Ableitung, falls in jedem Schritt die am weitesten rechts (bzw. links) stehende Variable ersetzt wird.

Beispiel: G = ({a, b},{S}, S,{S$\to$b, S$\to$aSS})

Linksableitung: S$\to$aSS$\to$aaSSS$\to$aabSS$\to$aabbS$\to$aabbaSS$\to$aabbabS$\to$aabbabb,

Rechtsableitung: S$\to$aSS$\to$aSaSS$\to$aSaSb$\to$aSabb$\to$aaSSabb$\to$aaSbabb$\to$aabbabb.

Zu jedem Ableitungsbaum gehören genau eine Rechts- und eine Links-Ableitung.

(D. h.: Grammatik G eindeutig
$\iff$ jedes w $\in$ l (G) besitzt genau eine Rechts-Ableitung
$\iff$ jedes w $\in$ l (G) besitzt genau eine Links-Ableitung.)