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: uw : $ \iff$v : uv = w

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

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

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

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

DL(G) Induktion über Wortlänge



Johannes Waldmann 2012-10-10