Rechts/Links-Ableitungen

Def: eine Ableitung w0$ \to_{G}^{}$w1$ \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.)



Johannes Waldmann 2006-02-02