Definition
Sei eine Kontextfreie Grammatik
Ein partieller Ableitungsbaum ist ein gewurzelter, geordneter Baum, dessen Knoten mit Symbolen aus beschriftet sind, so dass
- jeder innere Knoten mit einem Nichtterminalensymbol beschriftet ist.
- jedes Blatt mit einem Terminalsymbol oder Nichtterminalensymbol beschriftet ist.
- wenn ein innerer Knoten mit einen Nichtterminalensymbol beschriftet ist, so gibt es eine Ableitungsregel für die Kinder.
Bei einem vollständiger Ableitungsbaum
- ist die Wurzel mit S beschriftet.
- jedes Blatt mit einem Symbol aus beschriftet ist.
Beispiel
