Hallo,

wir hängen hier gerade ein wenig am Übungszettel 1 fest. Grammatiken zu produzieren geht noch, aber Aufgabe 3 wird böse. Nach der Durchsicht der F1 bis F4 Skripte haben wir allmählich das Gefühl die einzige vernünftige Methode zu zeigen, dass eine Grammatik eindeutig ist, ist für alle Worte zu zeigen, dass es nur genau eine Möglichkeit gibt dieses Wort zu erzeugen. Etwas zeitaufwändig bei unendlich vielen Worten. Welche Beweisverfahren habt ihr denn z.B. genutzt?

Naja, da gabs doch in F1 dieses tolle Verfahren, mit dem man etwas fuer alle Formeln zeigen konnte…

F1? Grammatiken sind erst in F2 eingeführt worden. Und wir möchten etwas für Grammatiken (nämlich deren Eindeutigkeit) zeigen, nicht für Formeln. %)
Das geht gerade um 180° entgegen der Richtung, die ich denke, dass es gehen muss.

Ja, aber alles, was von der Grammatik erzeugt wird, ist eine Formel.

Ja, aber alles, was von der Grammatik erzeugt wird, ist eine Formel.

und…???
wie man die Terminale der erzeugten Sprache interpretiert hat doch nichts mit der Eindeutigkeit der Grammatik zu tun??? oder bin ich jetzt total verwirrt???? :help:

Gut, also nochmal ausfuehrlicher :)

Wir wollen zeigen, dass die Grammatik eindeutig ist. Dazu muessen wir zeigen, dass jedes Wort, dass von der Grammatik erzeugt wird, einen eindeutigen Ableitungsbaum besitzt.

Jedes erzeugte Wort ist eine Formel, besitzt also eine gewisse Struktur. Und diese Struktur nutzen wir jetzt fuer den Beweis aus.

Ich bemerk gerade, dass das fuer den 2. Beweis wirklich _ziemlich_ kompliziert wird, wenn mans sauber aufschreiben will… aber zumindest der 1. Beweis sollte so gehen.

Noch 'ne andere Beweismoeglichkeit, um die Eindeutigkeit zu zeigen: Man zeigt, dass fuer jedes Nonterminal und jedes Teilwort der n\"achste Ableitungsschritt eindeutig bestimmt ist. Damit geht auch der zweite Beweis recht schmerzfrei (zumindest fuer meine Grammatik, kann ja sein, dass ihr andere habt).