Def: der Rand eines geordneten, markierten Baumes (T, m) ist die Folge aller Blatt-Markierungen (von links nach rechts).
Beachte: die Blatt-Markierungen sind
{
}
,
d. h. Terminalwörter der Länge 0 oder 1.
Für Blätter: rand(b) = m(b), für innere Knoten: rand(k) = rand(k1)rand(k2)...rand(kn)
Satz:
w L(G)
existiert Ableitungsbaum (T, m) für G
mit
rand(T, m) = w.