Dyck-Sprache

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen
Dieser Artikel oder nachfolgende Abschnitt ist nicht hinreichend mit Belegen (beispielsweise Einzelnachweisen) ausgestattet. Angaben ohne ausreichenden Beleg könnten demnächst entfernt werden. Bitte hilf Wikipedia, indem du die Angaben recherchierst und gute Belege einfügst.

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 .