Dyck-Sprache
# Dyck-Sprache

Die Dyck-Sprachen sind in der theoretischen Informatik bestimmte kontextfreie formale Sprachen, also Typ-2-Sprachen entsprechend der Chomsky-Hierarchie. Sie sind nach dem Mathematiker Walther von Dyck benannt.

Für jede natürliche Zahl $n$ ist die Dyck-Sprache $D_{n}$ die Wortmenge der korrekt geklammerten (wohlgeformten) Ausdrücke mit $n$ unterschiedlichen Klammerpaaren. Induktiv lässt sich $D_{n}$ wie folgt definieren:

* $\varepsilon \in D_{n}$ (Dabei ist $\varepsilon$ das leere Wort.)
* Falls $v,w\in D_{n}$, so gilt auch $vw\in D_{n}$.
* Falls $w\in D_{n}$, so gilt auch $\{_{i}w\}_{i}\in D_{n}$ für alle $i\in \{1,2,\dotsc ,n\}$. (Dabei sind $\{_{i}$ die $i$-te öffnende und $\$ die $i$-te schließende Klammer.)

Die Dyck-Sprache $D_{2}$ kann die zwei Klammerpaare [, ] und (, ) umfassen. Dann gilt beispielsweise:

* $[[(\,)[\,]](\,)]\in \ D_{2}$
* $([\,)]\notin \ D_{2}$
* $))\notin \ D_{2}$

Ein Wort aus einer Dyck-Sprache kann man zu einem leeren Wort reduzieren, indem man schrittweise jedes in der richtigen Reihenfolge auftretende Klammerpaar durch das leere Wort $\varepsilon$ ersetzt. Ein Dyck-Wort kann als ein Rutishauser-Klammergebirge dargestellt werden. Dabei wird auf der Abszisse die Position der Klammer im Wort und auf der Ordinate die jeweilige Klammertiefe dargestellt. Dyck-Sprachen sind deterministisch kontextfrei und damit insbesondere kontextfrei. Sie sind jedoch nicht regulär.

Kontextfreie Grammatik der Dyck-Sprache $D_{2}$:

    $S\rightarrow \varepsilon$
    $S\rightarrow SS$
    $S\rightarrow [S]$
    $S\rightarrow (S)$

Im Falle $D_{n}$ gibt es analog $n$ verschiedene Produktionen der Art $S\rightarrow \{_{i}S\}_{i}$ für $i\in \{1,2,\dotsc ,n\}$.

