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:

• $\epsilon \in D_n$ (Dabei ist $\epsilon$ 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,\dots ,n\}$. (Dabei sind ${\{}_i$ die $i$-te öffnende und ${\}}_i$ 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 $\epsilon$ 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\to \epsilon$

$S\to SS$

$S\to [S]$

$S\to (S)$

Im Falle $D_n$ gibt es analog $n$ verschiedene Produktionen der Art $S\to {\{}_{i}S{\}}_i$ für $i\in \{1,2,\dots ,n\}$.

Literatur

• Salomaa, Arto K.: Formale Sprachen. Springer, Berlin Heidelberg New York, 1978