Ableitungsbäume für CF-Sprachen

Id

Def: ein geordneter Baum T mit Markierung m : T→Σ∪{ε}∪V ist Ableitungsbaum für eine CF-Grammatik G , wenn:

• für jeden inneren Knoten k von T gilt m(k)∈V
• für jedes Blatt b von T gilt m(b)∈Σ∪{ε}
• für die Wurzel w von T gilt m(w) = S(G) (Startsymbol)
• für jeden inneren Knoten k von T mit Kindern k₁, k₂,…, k_n gilt (m(k), m(k₁)m(k₂)…m(k_n))∈R(G) (d. h. jedes m(k_i)∈V∪Σ )
• für jeden inneren Knoten k von T mit einzigem Kind k₁ = ε gilt (m(k), ε)∈R(G) .