+- FB18.de - Das Informatikforum ( /mybb )
+-- Forum: Diplom Informatik ( /forumdisplay.php?fid=114 )
+--- Forum: Theoretische Informatik (HS) ( /forumdisplay.php?fid=75 )
+--- Thema: LOS Übungszettel 1 ( /showthread.php?tid=4910 )
LOS Übungszettel 1 - Vollkorn - 07.04.2006 22:09
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?
Re: LOS Übungszettel 1 - UncleOwen - 07.04.2006 22:43
Naja, da gabs doch in F1 dieses tolle Verfahren, mit dem man etwas fuer alle Formeln zeigen konnte...
Re: LOS Übungszettel 1 - Vollkorn - 07.04.2006 22:55
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.
Re: LOS Übungszettel 1 - UncleOwen - 08.04.2006 00:25
Ja, aber alles, was von der Grammatik erzeugt wird, ist eine Formel.
Re: LOS Übungszettel 1 - Azrael - 08.04.2006 01:21
Zitat:
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:
Re: LOS Übungszettel 1 - UncleOwen - 08.04.2006 01:27
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.
Re: LOS Übungszettel 1 - UncleOwen - 08.04.2006 01:44
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.
Re: LOS Übungszettel 1 - UncleOwen - 08.04.2006 14:16
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).