Klammer-Sprachen

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

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

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

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

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

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

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

L(G)⊆D mathend000# Induktion über Länge der Ableitung

D⊆L(G) mathend000# Induktion über Wortlänge