Dyck-Sprachen

Dyck-Sprachen

Eine Dyck-Sprache Dn über n, benannt nach dem Mathematiker Walther von Dyck, ist die Wortmenge der richtig geklammerten (wohlgeformten) Ausdrücke mit n unterschiedlichen Klammerpaaren. Die Dyck-Sprache D2 kann die zwei Klammerpaare [] und () umfassen. Dann gilt beispielsweise

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

  • S --> \varepsilon
  • S --> SS
  • S --> [S]
  • S --> (S)

Für Dn gibt es entsprechend n Produktionen der Art S --> {S}.


Wikimedia Foundation.

Игры ⚽ Нужен реферат?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Dyck-Sprache — Dyck Sprachen sind ein Begriff aus der theoretischen Informatik und bezeichnet eine Menge von kontextfreien formalen Sprachen, also Typ 2 Sprachen entsprechend der Chomsky Hierarchie. Sie sind nach dem Mathematiker Walther von Dyck benannt. Die… …   Deutsch Wikipedia

  • Walther von Dyck — Büste von Walther von Dyck Walther Franz Anton von Dyck (* 6. Dezember 1856 in München; † 5. November 1934 ebenda) war ein deutscher Mathematiker. Inhaltsverzeichnis 1 Leben …   Deutsch Wikipedia

  • Salm-Dyck, Constanze, Fürstin zu — Salm Dyck, Constanze, Fürstin zu, Constanze, Fürstin zu, geb. Freiin von Theis, die älteste aller noch lebenden berühmten Schriftstellerinnen Frankreichs, wurde zu Nantes am 7. Nov. 1767 geb. 1786 erschien ihr erstes lyrisches Produkt: »Bouton de …   Damen Conversations Lexikon

  • Dycksprache — Eine Dyck Sprache Dn über n, benannt nach dem Mathematiker Walther von Dyck, ist die Wortmenge der richtig geklammerten (wohlgeformten) Ausdrücke mit n unterschiedlichen Klammerpaaren. Die Dyck Sprache D2 kann die zwei Klammerpaare [] und ()… …   Deutsch Wikipedia

  • Zuname — Ein Familienname (auch Nachname, Zuname oder amtsdeutsch einfach Name) dient als Ergänzung zum Vornamen zur besseren Unterscheidbarkeit von Personen. Im Hochdeutschen steht nach dem Vornamen und eventuellen Zwischennamen der Familienname an… …   Deutsch Wikipedia

  • Familiennamen — Ein Familienname (auch Nachname, Zuname oder amtsdeutsch einfach Name) dient als Ergänzung zum Vornamen zur besseren Unterscheidbarkeit von Personen. Im Hochdeutschen steht nach dem Vornamen und eventuellen Zwischennamen der Familienname an… …   Deutsch Wikipedia

  • Herkunftsname — Ein Familienname (auch Nachname, Zuname oder amtsdeutsch einfach Name) dient als Ergänzung zum Vornamen zur besseren Unterscheidbarkeit von Personen. Im Hochdeutschen steht nach dem Vornamen und eventuellen Zwischennamen der Familienname an… …   Deutsch Wikipedia

  • Mädchenname — Ein Familienname (auch Nachname, Zuname oder amtsdeutsch einfach Name) dient als Ergänzung zum Vornamen zur besseren Unterscheidbarkeit von Personen. Im Hochdeutschen steht nach dem Vornamen und eventuellen Zwischennamen der Familienname an… …   Deutsch Wikipedia

  • Nachname — Ein Familienname (auch Nachname, Zuname oder amtsdeutsch einfach Name) dient als Ergänzung zum Vornamen zur besseren Unterscheidbarkeit von Personen. Im Hochdeutschen steht nach dem Vornamen und eventuellen Zwischennamen der Familienname an… …   Deutsch Wikipedia

  • D.G. Monrad — Ditlev Gothard Monrad Monrad in seinen späten Jahren Ditlev Gothard Monrad (* 24. November 1811 in Kopenhagen; † 28. März …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”