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 <math>n</math> ist die Dyck-Sprache <math>D_n</math> die Wortmenge der korrekt geklammerten (wohlgeformten) Ausdrücke mit <math>n</math> unterschiedlichen Klammerpaaren. Induktiv lässt sich <math>D_n</math> wie folgt definieren:
- <math>\varepsilon \in D_n</math> (Dabei ist <math>\varepsilon</math> das leere Wort.)
- Falls <math>v,w \in D_n</math>, so gilt auch <math>vw\in D_n</math>.
- Falls <math>w \in D_n</math>, so gilt auch <math>\{_i w \}_i \in D_n</math> für alle <math>i\in\{1,2,\dotsc,n\}</math>. (Dabei sind <math>\{_i</math> die <math>i</math>-te öffnende und <math>\}_i</math> die <math>i</math>-te schließende Klammer.)
Die Dyck-Sprache <math>D_2</math> kann die zwei Klammerpaare [, ] und (, ) umfassen. Dann gilt beispielsweise:
- <math>[[(\,)[\,]](\,)] \in\ D_2</math>
- <math>([\,)] \notin\ D_2</math>
- <math>)) \notin\ D_2</math>
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 <math>\varepsilon</math> 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.
Kontextfreie Grammatik der Dyck-Sprache <math>D_2</math>:
- <math>S \rightarrow \varepsilon</math>
- <math>S \rightarrow SS</math>
- <math>S \rightarrow [S]</math>
- <math>S \rightarrow (S)</math>
Im Falle <math>D_n</math> gibt es analog <math>n</math> verschiedene Produktionen der Art <math>S \rightarrow \{_i S \}_i</math> für <math>i\in\{1,2,\dotsc,n\}</math>.
Literatur
- Salomaa, Arto K.: Formale Sprachen. Springer, Berlin Heidelberg New York, 1978