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

  • \varepsilon \in D_n (Dabei ist \varepsilon das leere Wort.)
  • Falls v,w \in D_n, so gilt auch vw\in D_n.
  • Falls w \in D_n, so gilt auch \{_i w \}_i \in D_n für alle i\in\{1,2,\dotsc,n\}. (Dabei ist \{_i die i-te öffnende Klammer.)

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

  • [[()[]]()] \in\ D_2
  • ([)] \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_2:

S \rightarrow \varepsilon
S \rightarrow SS
S \rightarrow [S]
S \rightarrow (S)

Für D_n gibt es entsprechend n Produktionen der Art S \rightarrow \{S\}.