217.6.228.105 am 9. Februar 2023 um 13:44 Uhr

2023-02-09T13:44:20Z

Neue Seite

Die '''Dyck-Sprachen''' sind in der [[Theoretische Informatik|theoretischen Informatik]] bestimmte [[Kontextfreie Sprache|kontextfreie]] [[formale Sprache]]n, 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. [[Strukturelle Induktion|Induktiv]] lässt sich <math>D_n</math> wie folgt definieren:
*<math>\varepsilon \in D_n</math> (Dabei ist <math>\varepsilon</math> das [[Leeres Wort|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 [[Heinz Rutishauser|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 kontextfreie Sprache|deterministisch kontextfrei]] und damit insbesondere [[Kontextfreie Sprache|kontextfrei]]. Sie sind jedoch nicht [[Reguläre Sprache|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

[[Kategorie:Compilerbau]]
[[Kategorie:Theorie formaler Sprachen]]

Dyck-Sprache - Versionsgeschichte

217.6.228.105 am 9. Februar 2023 um 13:44 Uhr