Dyck-Sprache
aus Wikipedia, der freien Enzyklopädie
Eine Dyck-Sprache Dn ü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 D2 kann die zwei Klammerpaare [] und () umfassen. Dann gilt beispielsweise
![[[()[]]()] \in\ D_2](../../../math/f/2/9/f2964ee04f6dcf5170a312d009fd499e.png)
, aber![([)] \notin\ D_2](../../../math/f/9/1/f913bb7f238726d5f81ff5312468d9bb.png)
Ein Wort aus einer Dyck-Sprache kann man zu einem leeren Wort reduzieren, indem man schrittweise jedes in der richtigen Reihenfolge auftretendes Klammerpaar durch das leere Wort 
ersetzt. Ein Dyck-Wort kann als ein nach Heinz Rutishauser benanntes Klammergebirge dargestellt werde. Dabei wird auf der Abszisse die Position der Klammer im Wort und auf der Ordinate die jeweilige Klammertiefe dargestellt. Dyck-Sprachen sind kontextfrei aber nicht regulär.
