Klammer-Sprachen

Abstraktion von vollständig geklammerten Ausdrücke mit zweistelligen Operatoren

(4*(5+6)-(7+8)) ⇒ (()()) ⇒aababb

Höhendifferenz: h : {a, b}^*→$\mathbb {Z}$ : w $\mapsto$ | w|_a - | w|_b

Präfix-Relation: u≤w : $\iff$∃v : u⋅v = w

Dyck-Sprache: D = {w | h(w) = 0∧∀u≤w : h(u)≥0}

CF-Grammatik: G = ({a, b},{S},{S→ε, S→aSbS})

Satz: L(G) = D. Beweis (Plan):

L(G)⊆D strukturelle Induktion über Ableitungsbaum

D⊆L(G) Konstruktion eines Ableitungsbaumes