Dyck-Sprachen

Eine Dyck-Sprache D_n über n, benannt nach dem Mathematiker Walther von Dyck, ist die Wortmenge der richtig geklammerten (wohlgeformten) Ausdrücke mit n unterschiedlichen Klammerpaaren. Die Dyck-Sprache D₂ kann die zwei Klammerpaare [] und () umfassen. Dann gilt beispielsweise

• $[[()[]]()] \in\ D_2$, aber
• $([)] \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.

Grammatik der Dyck-Sprache D₂:

• S --> $\varepsilon$
• S --> SS
• S --> [S]
• S --> (S)

Für D_n gibt es entsprechend n Produktionen der Art S --> {S}.