Dyck-Sprache

[system]

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

[semmy]

Dyck-Sprache
Dyck-Sprache ist ja die Sprache der Klammerausdrücke. Wenn man ein Wort aus Dyck-Sprache gegeben hat, wie rekonstruiert man daraus ein B-Baum?

[Der_Ich]

---

naja für öffnende klammern gehts links runter und für schließende rechts

(()())

      o
   |     |
   o     o
|    |  |    |
o    o  o    o

[bRownY]

---

\o/
/\o/
/\o/
/\o/
/\o/
/\o/
/\o/
/\o/
/\o/>>
/>>>>>>>>>

[Lup]

---

Vorsicht, das funktioniert hier anders:
Das Beispiel von Der Ich, also (()()) bzw. 001011, entspricht folgendem Baum:
[m]
O
/
O X
/
X O
/
X X
[/m]
Ein innerer Knoten (O) entspricht einer öffnenden Klammer, ein Blatt (X) einer schließenden, wobei das letzte Blatt im Dyck-Wort immer fehlt.
Will man nun umgekehrt von dem Wort auf den Baum kommen, fügt man einfach immer “so weit links wie möglich” das jeweils nächste Symbol an.

[Der_Ich]

---

Ok, defintionssache

[semmy]

---

@Lup

Vorsicht, das funktioniert hier anders:
Das Beispiel von Der Ich, also (()()) bzw. 001011, entspricht folgendem Baum:
[m]
O
/
O X
/
X O
/
X X
[/m]
Ein innerer Knoten (O) entspricht einer öffnenden Klammer, ein Blatt (X) einer schließenden, wobei das letzte Blatt im Dyck-Wort immer fehlt.
Will man nun umgekehrt von dem Wort auf den Baum kommen, fügt man einfach immer „so weit links wie möglich“ das jeweils nächste Symbol an.

supi, danke!!

[miniwahr]

---

@Lup

Will man nun umgekehrt von dem Wort auf den Baum kommen, fügt man einfach immer „so weit links wie möglich“ das jeweils nächste Symbol an.

jupp, das ist wichtig, damit entsteht die rekursive Struktur.