\begin{slide}{Klammer-Sprachen}

\parskip 5mm

\newcommand{\ZZ}{\mathbb{Z}}

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

\verb|(4*(5+6)-(7+8))|
$\Rightarrow$ \verb|(()())| $\Rightarrow aababb$

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

Präfix-Relation: $u \le w :\iff \exists v: u\cdot v = w$

Dyck-Sprache: $D=\{w \mid h(w)=0 \wedge \forall u\le w: h(u)\ge 0\}$

CF-Grammatik: $G = (\{a,b\},\{S\},S,\{S\to\epsilon,S\to aSbS\})$

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

$L(G)\subseteq D$ Induktion über Länge der Ableitung

$D\subseteq L(G)$ Induktion über Wortlänge


\end{slide}
