Rechtsableitung
aus Wikipedia, der freien Enzyklopädie
Rechtsableitung und Linksableitung sind Begriffe aus der Theoretischen Informatik.
Wenn bei einer Ableitung immer das am weitesten rechts (links) stehende Nichtterminalsymbol einer formalen Grammatik ersetzt wird, so spricht man von Rechtsableitung (Linksableitung).
Ein Rechtsableitungsschritt wird formal defininiert durch
und ein Linksableitungsschritt durch
bei dem die Regel 
angewandt wurde. Dabei bedeuten:
- w ist eine Zeichenkette und besteht nur aus Terminalsymbolen
- A ist ein Nichtterminalsymbol der linken Seite der anzuwendenden Regel.
- α,β,γ und δ sind Zeichenketten, die aus Terminal- und Nichtterminalsymbolen bestehen.
Bei kontextfreien Grammatiken ist stets δ = γ = ε. Wenn zu einem Wort mehrere verschiedene Rechts-/Linksableitungen existieren, heißt die Grammatik mehrdeutig.
[Bearbeiten] Beispiel
Grammatik:
Startsymbol: S
Linksableitung:
Rechtsableitung:
