Ableitungsbäume (II)

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

Beachte: die Blatt-Markierungen sind ∈{ε}∪Σ mathend000#, d. h. Terminalwörter der Länge 0 oder 1.

Für Blätter: rand(b) = m(b) mathend000#, für innere Knoten: rand(k) = rand(k₁)rand(k₂)…rand(k_n) mathend000#

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