Id: baum.tex,v 1.1 2006-10-16 19:50:57 waldmann Exp
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
k1, k2,..., kn gilt
(m(k), m(k1)m(k2)...m(kn)) R(G)
(d. h. jedes
m(ki) V )
- für jeden inneren Knoten k von T
mit einzigem Kind
k1 = gilt
(m(k),) R(G).
Johannes Waldmann
2007-01-23