[FoSAP] Äquivalenz von Ableitungsbäumen

[$veno]

Hi!

Sind folgende Ableitungsbäume äquivalent oder nicht?

Code: Alles auswählen

                     S
                    /  \
                  A     A
                  |    /  \
                 bb   A    A
                      |    |
                      b    b         

               
                     S
                    /  \
                  A     A
                /  \    |
               A    A   bb
               |    |
               b    b


Ich denke mal diese sind gleich oder?
Wenn sie nicht äquivalent sind, dann hieße das doch, dass die Grammatik durch den dieser Ableitungsbaum hervorgegangen ist mehrdeutig ist.

Gruss Sven

[Pillenfresser]

Jetzt wirds langsam exotisch. Ableitungsbäume hatten wir ja (hoffentlich) nicht in den Übungen.

Wann und ob man bei Ableitungsbäumen von Äquivalenz sprechen kann weiß ich nicht. Aber wenn diese beiden Bäume aus der selben Grammatik gefolgert werden können hast du bewiesen, dass die Grammatik mehrdeutig ist. Ich glaub zu mehr war die Definition in der Vorlesung auch nicht gut.

[RammboNr5]

die Bäume sind ja nur seitenverkehrt, von daher mit Sicherheit äquivalent würde ich sagen.

Und die Grammatik dazu ist 100% mehrdeutig

[$veno]

die Bäume sind ja nur seitenverkehrt, von daher mit Sicherheit äquivalent würde ich sagen.

Und die Grammatik dazu ist 100% mehrdeutig

Hmm, das widerspricht sich jetzt aber, damit eine KFG mehrdeutig ist dürfen diese ja gerade nicht äquivalent sein

[nomawie]

nein die bäume sind nicht äquivalent. das eine ist ne linksableitung, das andere ne rechtsableitung

[Muffi]

die Bäume sind ja nur seitenverkehrt, von daher mit Sicherheit äquivalent würde ich sagen.

Und die Grammatik dazu ist 100% mehrdeutig

Hmm, das widerspricht sich jetzt aber, damit eine KFG mehrdeutig ist dürfen diese ja gerade nicht äquivalent sein

Richtig. Eine Grammatik ist mehrdeutig, wenn es mindestens zwei verschiedene Rechts- oder mindestens zwei verschiedene Linksableitungen gibt. Eine Rechts- und eine Linksableitung sind nicht hinreichend für Mehrdeutigkeit!

[nomawie]

Richtig. Eine Grammatik ist mehrdeutig, wenn es mindestens zwei verschiedene Rechts- oder mindestens zwei verschiedene Linksableitungen gibt. Eine Rechts- und eine Linksableitung sind nicht hinreichend für Mehrdeutigkeit!

Nö, es reicht wenn es eine Rechts und eine Linksableitung gibt

[oxygen]

Richtig. Eine Grammatik ist mehrdeutig, wenn es mindestens zwei verschiedene Rechts- oder mindestens zwei verschiedene Linksableitungen gibt. Eine Rechts- und eine Linksableitung sind nicht hinreichend für Mehrdeutigkeit!

Nö, es reicht wenn es eine Rechts und eine Linksableitung gibt

Nö. Muffi hat Recht. Links und Rechtsseitige Ableitungen müssen jeweils Eindeutig sein.

[p0llux]

Nö.

[Pillenfresser]

Ich würde aus meinen Aufzeichnungen interpretieren, dass eine Links- und eine Rechtsableitung reichen.

[nomawie]

Hab eben das Wort "verschieden" vergessen zu schreiben. Da wir von Mehrdeutigkeit reden, bin ich davon ausgegangen. Natürlich dürfen die Links und Rechtsableitung nicht gleich sein wie es bei einer solchen Regel wäre

S->aBa
B->b

Wenn man ein Wort nur rechtsableitet kommt immer der gleiche Baum raus. Es kann keine zwei verschiedenen Rechtsableitungsbäume geben (jedenfalls wüsste ich gerade nicht wie das gehen soll)

[oxygen]

In meinen Aufzeichungen steht:
Def:
G heißt eindeutig, wenn es für jedes Wort aus L(G) genau einen Ableitungsbaum gibt.
...
Satz:
w besitzt zwei Ableitungsbäume gdw wenn w über zwei Links- oder Rechtsableitungen verfügt.

Hm.

[Pillenfresser]

Wenn man ein Wort nur rechtsableitet kommt immer der gleiche Baum raus. Es kann keine zwei verschiedenen Rechtsableitungsbäume geben (jedenfalls wüsste ich gerade nicht wie das gehen soll)

Rechtsableitung heißt nur, dass das immer das rechteste Nichtterminal ersetzt wird, aber nicht wodurch. Kann also viele verschiedene geben.

[Muffi]

Wenn man ein Wort nur rechtsableitet kommt immer der gleiche Baum raus. Es kann keine zwei verschiedenen Rechtsableitungsbäume geben (jedenfalls wüsste ich gerade nicht wie das gehen soll)

Nimm eine Grammatik vom Typ 1:

S -> aBCc
aB -> ab
B -> b
C -> c

S => aBCc => abCc => abcc
S => abCc => abcc

sind zwei verschiedene Linksableitungen.

[$veno]

Hmm, also, irgendwie verwirrst mich das alles jetzt, wie isses denn nun? Sind die Bäume nun gleich oder nicht und ist die Grammatik dann mehrdeutig?

Gruss sven