Diskussion:Greibach-Normalform

aus Wikipedia, der freien Enzyklopädie

Was ist das????--HansG 18:54, 20. Feb 2004 (CET)

Ein sehr theoretischer Begriff, der leider erst eine gewisse Bedeutung erlangt, wenn man sich im Bereich Theoretische Informatik etwas vorgearbeitet hat. Stern 18:59, 20. Feb 2004 (CET)

AHA!--HansG 19:07, 20. Feb 2004 (CET)

Jungs, könnte man diese Dinge nicht für den Laien verständlich schreiben? --Felipe

Kann ich mir nur sehr schwer vorstellen. Diejenigen, die mit dem Artikel in Kontakt kommen, haben aber das nötige Vorwissen. Die Frage ist also, ob man es überhaupt allgemeinverständlicher formulieren muss, wenn es denn ginge. Stern !? 00:14, 4. Feb 2005 (CET)

Ich habe jetzt eine Einleitung formuliert. Jemand, der von dem Artikel nur Bahnhof versteht, sollte nun schon in der Einleitung merken, dass er hier falsch ist.--MKI 16:09, 26. Mär 2005 (CET)

Sollte man nicht den Sonderfall (S Startsymbol) zulassen, um auch abzuhaken und alle kontextfreien Grammatiken zu erwischen?

Die Überführung von der Chomsky in die Greibach Normalform erscheint mir irgendwie ein wenig unsauber. Bei mir blieben einige Fragen offen. Was hat es mit der Nummerierung der A_i auf sich? Woher kommt diese? Ist sie wahllos oder muss sie nach einem bestimmten Schema vorgenommen werden? Ich habe in der Überschrift eine kurze Variablendeklaration hinzugefügt. Bei dem y war ich mir nicht sicher - wenn ich es jedoch richtig verstanden habe so war dieses auch eine Folge von Nichtterminalen. Eine etwas ausführlichere Beschreibung des Algorithmus fände ich sehr schön. So wie er jetzt ist finde ich ihn sehr unverständlich, da Variablen und Produktionen "aus dem Nichts" auftauchen ohne große Beschreibung. So wie er jetzt ist habe ich ihn leider nicht verstanden. --Horratio 16:35, 8. Feb 2006 (CET)

Der Abschnitt "Konstruktion der GNF" ist schwer verständlich, sehr unvollständig und teilweise falsch. Müsste man wohl ganz von vorne aufrollen. Leider weis ich auch nicht wie diese Mathecodes funktionieren. Also kann ich nicht viel dran machen. Man muüsste den Abschnitt löschen und ganz neu erstellen. --80.137.150.184 13:05, 25. Jun 2006 (CEST)

[Bearbeiten] 2 - Greibach Normalform

Ich habe den Abschnitt über "Eine strengere Version der Greibach Normalform" umbenannt in "2 - Greibach Normalform" (so wurde sie zumindest bei mir in der Vorlesung genannt) und den Text ein wenig umgeschrieben. --Horratio 16:49, 8. Feb 2006 (CET)

Und ich habe das wieder rückgängig gemacht. Den Bezeichner 2GNF sollten wir nur dann benutzen, wenn er in der Fachliteratur verbreitet ist. Dass ein einzelnes Vorlesungsskript dazu als Beleg nicht ausreicht, sollte klar sein.--MKI 19:08, 8. Feb 2006 (CET)

Buch von Prof. Dr. Norbert Blum, Theoretische Informatik - eine Anwendungsorientierte Einführung. Auf Seite 181 wird ganz explizit die 2GNF mit diesem Namen als solche eingeführt. Ich habe noch die Bücher von Baier und Schöning hier liegen welche nur die GNF einführen - ohne Erweiterung. Was jetzt "richtiger" ist kann ich leider nicht sagen. Ich überlasse es dir. --Horratio 19:42, 8. Feb 2006 (CET)

Im Schöning wird die strengere Variante schon erwähnt: Wir bemerken anschließend noch, dass man jede kontextfreie Grammatik so in Greibach Normalform umforman kann, dass auf der rechten Seite der Regeln nicht mehr als 2 Variablen vorkommen.

Es geht mir aber eigentlich weniger um die Abkürzung 2GNF (Informatiker scheinen derartigen Abkürzungen zu mögen, vgl. 3SAT), sondern um die Überschrift 2 - Greibach Normalform. Diese sah nicht gut aus, die Alternative Eine strengere Version der Greibach Normalform finde ich wesentlich besser. Wenn die Abkürzung 2GNF allgemein verbreitet ist, dann können und sollten wir sie im Artikel aufführen. Ich glaube aber nicht, dass sie sehr verbreitet ist. eine Google-Suche nach "GNF2 Greibach" liefert kein Ergebnis.--MKI 23:10, 8. Feb 2006 (CET)

[Bearbeiten] Spezialfall k=1

Hallo!

Wie im Artikel beschrieben ist k=1 ein spezialfall, da sich eine reguläre Sprache ergibt. Müsste man nicht auch noch k=0 hinzufügen?

Gruß!

[Bearbeiten] Halbwissen

Der Abschnitt mit dem "der Rest ist Halbwissen" klingt schlecht.