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:

$ε \in D_{n}$ (Dabei ist $ε$ das leere Wort.)
Falls $v, w \in D_{n}$ , so gilt auch $v w \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 $ε$ 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 ε

S \to S S

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