Dyck-Sprache

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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 ist die -te öffnende 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 :

Für gibt es entsprechend Produktionen der Art .