Dyck-Sprache

Dyck-Sprachen sind ein Begriff aus der theoretischen Informatik und bezeichnet eine Menge von kontextfreien formalen Sprachen, also Typ-2-Sprachen entsprechend der Chomsky-Hierarchie. Sie sind nach dem Mathematiker Walther von Dyck benannt.

Die Dyck-Sprache D_n ist die Wortmenge der korrekt geklammerten (wohlgeformten) Ausdrücke mit n unterschiedlichen Klammerpaaren. Die Dyck-Sprache D₂ 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.

Grammatik der Dyck-Sprache D₂:

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

Für D_n gibt es entsprechend n Produktionen der Art $S \rightarrow \{S\}$.