Ableitungsbäume (II)

Def: der Rand eines geordneten, markierten Baumes (T, m) ist die Folge aller Blatt-Markierungen (von links nach rechts).

Beachte: die Blatt-Markierungen sind $\in$ {$\epsilon$} $\cup$ $\Sigma$, 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(k₁)rand(k₂)...rand(k_n)

Satz: w $\in$ L(G)$\iff$ existiert Ableitungsbaum (T, m) für G mit rand(T, m) = w.