mathend000#
Def: ein geordneter Baum T
mathend000#
mit Markierung
m : T→Σ∪{ε}∪V
mathend000#
ist Ableitungsbaum für eine CF-Grammatik G
mathend000#, wenn:
- für jeden inneren Knoten k
mathend000# von T
mathend000# gilt
m(k)∈V
mathend000#
- für jedes Blatt b
mathend000# von T
mathend000# gilt
m(b)∈Σ∪{ε}
mathend000#
- für die Wurzel w
mathend000# von T
mathend000# gilt m(w) = S(G)
mathend000# (Startsymbol)
- für jeden inneren Knoten k
mathend000# von T
mathend000#
mit Kindern
k1, k2,…, kn
mathend000# gilt
(m(k), m(k1)m(k2)…m(kn))∈R(G)
mathend000#
(d. h. jedes
m(ki)∈V∪Σ
mathend000#)
- für jeden inneren Knoten k
mathend000# von T
mathend000#
mit einzigem Kind
k1 = ε
mathend000# gilt
(m(k), ε)∈R(G)
mathend000#.
Johannes Waldmann
2014-03-31