Ableitungsbäume für CF-Sprachen

Id: baum.tex,v 1.2 2005/11/02 23:37:52 waldmann Exp

Def: ein geordneter Baum T mit Markierung m : T$\to$$\Sigma$ $\cup$ {$\epsilon$} $\cup$ V ist Ableitungsbaum für eine CF-Grammatik G, wenn:

• für jeden inneren Knoten k von T gilt m(k) $\in$ V
• für jedes Blatt b von T gilt m(b) $\in$ $\Sigma$ $\cup$ {$\epsilon$}
• 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)) $\in$ R(G) (d. h. jedes m(k_i) $\in$ V $\cup$ $\Sigma$)
• für jeden inneren Knoten k von T mit einzigem Kind k₁ = $\epsilon$ gilt (m(k),$\epsilon$) $\in$ R(G).