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 ${\displaystyle n}$ ist die Dyck-Sprache ${\displaystyle D_{n}}$ die Wortmenge der korrekt geklammerten (wohlgeformten) Ausdrücke mit ${\displaystyle n}$ unterschiedlichen Klammerpaaren. Induktiv lässt sich ${\displaystyle D_{n}}$ wie folgt definieren:

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

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

• ${\displaystyle [[(\,)[\,]](\,)]\in \ D_{2}}$
• ${\displaystyle ([\,)]\notin \ D_{2}}$
• ${\displaystyle ))\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 ${\displaystyle \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 ${\displaystyle D_{2}}$:

${\displaystyle S\rightarrow \varepsilon }$

${\displaystyle S\rightarrow SS}$

${\displaystyle S\rightarrow [S]}$

${\displaystyle S\rightarrow (S)}$

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