Ableitungsbaum für kontextfreie Grammatik

Wissenschaft Mathematik
#1

Hallo!

Ich habe Probleme beim Lösen einer Aufgabe. Sie betrifft kontextfreie Grammatiken.

Folgende kontextfreie Grammatik ist gegeben:
G = ({S}, {(,)}, {S -> (S) | SS | ε}, S)

Übersichtshalber notiere ic die Regeln wie folgt:
S -> ε
S -> (S)
S -> SS

Nun möchte ich dazu gerne einen Ableitungsbaum für das Wort w = ()((())()) erstellen.

Die erste Klammer zu erstellen ist kein Problem (siehe Bild), bei den restlichen weiss ich aber leider nicht, wie ich vorgehen soll.
Kann mir jemand einen Tipp geben?

Bild: http://s7.directupload.net/images/130530/ajhgg9tx.png

#2

Hallo,

in dem Fall müsstest du einfach nur die zusammengehörigen Klammern auf derselben Ebene zählen:

()((())())
1112332221

Also haben wir zwei Klammerpaare auf der ersten Ebene.
Also S->SS
Den linken Baum davon hast du bereits. Für den rechten Baum bleibt:

(())()
233222

Da sind auch wieder zwei Klammerpaare auf derselben Ebene.
Also wieder S->SS
Der rechte Teilbaum davon ist der Teilbaum vom Anfang.
Für den linken Teilbaum bleibt dann:

(())
2332

Dafür brauchen wir offensichtlich
S->(S)
und es bleibt:

()
33

Und das ist auch wieder der Teilbaum vom Anfang.

#3

Jetzt habe ich es geschnallt!

Nachdem man sich das mit den Ebenen genau überlegt, leuchtet das ein. So müsste der Baum richtig aussehen?

http://s14.directupload.net/images/130530/4vkia7by.png

#4

Ja, sieht gut aus.