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

  • (Dabei ist das leere Wort.)
  • Falls , so gilt auch .
  • Falls , so gilt auch für alle . (Dabei sind die -te öffnende und die -te schließende Klammer.)

Die Dyck-Sprache kann die zwei Klammerpaare [, ] und (, ) umfassen. Dann gilt beispielsweise:

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 :

Im Falle gibt es analog verschiedene Produktionen der Art für .

Literatur

  • Salomaa, Arto K.: Formale Sprachen. Springer, Berlin Heidelberg New York, 1978