Diskussion:Greibach-Normalform

Laienverständlichkeit

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)

Das leere Wort Teil einer GNF-Sprache?

Sollte man nicht den Sonderfall $S\rightarrow \varepsilon$ (S Startsymbol) zulassen, um auch $L=\{\varepsilon \}$ abzuhaken und alle kontextfreien Grammatiken zu erwischen?

Ja, à la Erk/Priese. Fände ich auch gut. -- UKoch 00:56, 10. Aug. 2011 (CEST)

Überarbeitung: Konstruktion der GNF

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)

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)

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ß!

Geändert -- Murmeltier 01:28, 23. Jun. 2007 (CEST)

Halbwissen

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

Erledigt? --Gms 23:32, 20. Aug. 2008 (CEST)

Quellenangaben

In Uwe Schöning "Theoretische Informatik kurz gefasst" steht zur Konstruktion der Geibach-Normalform nur "Wir erwähnen nur, dass die Konstruktion komplizierter ist, und dass der entsprechende Algorithmus exponentielle Laufzeit hat" (Seite 54, Korriegierter Nachdruck 1993). Der Algorithmus im referenzierten Skript hat nichts (oder zumindest nicht offensichtlich) mit dem beschriebenen Algorithmus zu tun. Außerdem widerspricht sich das Skript und Schöning bezüglich der Komplexität (exponentiell vs. O(R^3) (nicht signierter Beitrag von 78.50.197.41 (Diskussion | Beiträge) 13:08, 14. Mär. 2010 (CET))

Im Skript von Prof. Dr. Dorothea Wagner wird auf S. 104 ein Verfahren beschrieben. Ich kann allerdings gerade nicht spontan sagen, ob dieses Verfahren äquivalent zu dem in diesem Artikel ist und welche Laufzeit es hat.

edit: Auf S. 105 steht, dass Regel (i) ${\binom {m}{n}}$ mal angewandt wird, was ja in ${\mathcal {O}}(n^{2})$ ist. --MartinThoma 15:44, 9. Feb. 2012 (CET)

Wieso ist $\textstyle {\binom {m}{n}}$ in ${\mathcal {O}}(n^{2})$? -- UKoch (Diskussion) 18:37, 3. Mai 2012 (CEST)

Mit dem Algorithmus unter Binomialkoeffizient: Algorithmus zur effizienten Berechnung wird $n$-mal die Rechnung $(m-n+i)/i$ (für $i=1,...,n$) ausgeführt. Die Berechnung von $m-n+i$ ist in $\Theta (m)$ durchführbar; das Ergebnis ist kleiner als $m$, $i$ ebenso, daher ist die Division in ${\mathcal {O}}(m\cdot log(m)\cdot log(log(m)))$ (SRT-Division mit Schönhage-Strassen-Multiplikation) durchführbar. Ich würde also eher sagen, dass die Komplexität zur Berechnung von ${\binom {m}{n}}$ in ${\mathcal {O}}\left(n\cdot m\cdot log(m)\cdot log(log(m))\right)$ liegt.

EDIT: Hätte genauer lesen sollen… nicht die Komplexität der Berechnung von ${\binom {m}{n}}$ war gefragt, sondern ihre Größenordnung… ${\binom {m}{n}}\in {\mathcal {O}}(n^{2})$ stimmt sicherlich nicht, bereits ${\binom {n+3}{n}}={\frac {(n+1)(n+2)(n+3)}{6}}\in \Omega (n^{3})$. Allerdings ist im zitierten Skript von $\textstyle {\binom {m}{2}}$ (nicht $\textstyle {\binom {m}{n}}$) die Rede – dafür gilt dann allerdings $\textstyle {\binom {m}{2}}={\frac {m(m-1)}{2}}\in {\mathcal {O}}(m^{2})$… -- 80.171.218.233 16:23, 7. Jan. 2014 (CET)

Das im Artikel vorgestellte Verfahren funktioniert so gar nicht. Man betrachte die Grammatik:

${\begin{matrix}A_{0}&\to &a|A_{0}A_{1}|A_{1}A_{0}\\A_{1}&\to &a|A_{0}A_{1}|A_{1}A_{0}\end{matrix}}$

Umnumerieren ändert die Grammatik nicht. Nach dem ersten Einsetzungsschritt:

${\begin{matrix}A_{0}&\to &a|A_{0}A_{1}|A_{1}A_{0}\\A_{1}&\to &a|aA_{1}|A_{0}A_{1}A_{1}|A_{1}A_{0}A_{1}|A_{1}A_{0}\end{matrix}}$

Wir haben $A_{1}\to A_{0}A_{1}$ eliminiert, dafür aber $A_{1}\to A_{0}A_{1}A_{1}$ erhalten. Fährt man fort erhält man

${\begin{matrix}A_{0}&\to &a|A_{0}A_{1}|A_{1}A_{0}\\A_{1}&\to &a|aA_{1}|aA_{1}A_{1}|\ldots |aA_{1}^{k}|A_{0}A_{1}A_{1}^{k}|A_{1}A_{0}A_{1}^{k}|\ldots |A_{1}A_{0}A_{1}A_{1}|A_{1}A_{0}A_{1}|A_{1}A_{0}\end{matrix}}$

Es bleibt immer eine Produktion der Form $A_{1}\to A_{0}A_{1}A_{1}^{k}$ übrig, das Verfahren terminiert also nicht. Vermutlich klappt es, wenn man die Linksrekursionen zuerst entfernt und die $B_{i}$ „vor“ den $A_{i}$ in die Numerierung „einfügt“, um danach erst die Produktionen einzusetzen. Solche Analysen wären aber nicht Aufgabe von Wikipedia. Ich fände es besser, entweder den Algorithmus ganz zu entfernen oder vorerst nur die Transformationen und ihren Zweck anzugeben und für Details stattdessen auf externe Literatur zu verweisen. --Carsten Milkau (Diskussion) 16:33, 28. Aug. 2015 (CEST)

Ich hab den Abschnitt über die Konstruktion der Greibach-Normalform überarbeitet. Einige Kommentare zu dieser Diskussion (falls noch jemand die Diskussion verfolgen sollte ;)):

* In Uwe Schöning "Theoretische Informatik kurz gefasst" steht in der 5.Auflage eine Beschreibung des Algorithmus. Aus dem Vorwort geht hervor dass dieser Abschnitt in der 3.Auflage überarbeitet wurde.

* Das erwähnte Skript folgt dem Buch von Ingo Wegener.

* Beide Bücher beschreiben den gleichen Algorithmus aber in sehr unterschiedlicher Form. Wegener führt den Korrektheitsbeweis parallel zur Beschreibung des Algorithmus und führt entsprechend Invarianten etc ein. Schöning führt keinen Beweis und präsentiert nur den Algorithmus (das dafür aber in pseudocode).

* Die $\textstyle {\binom {m}{2}}$ Schranke im Wegener ist nur eine Schranke wie oft die beiden Methoden in Phase 1 aufgrufen werden. Diese Methoden haben aber keine konstante Laufzeit. Das impliziert also keine Schranke für die Laufzeit oder die Größe der resultierenden Grammatik in Greibach Normalform.

-- Wdvorak (Diskussion) 18:03, 21. Okt. 2017 (CEST)

Schöning-Quelle

"Schöning, 2001" genügt als Quellenangabe nicht. Ist damit "Theoretische Informatik - kurzgefasst." mit der ISBN 3827410991 oder "Algorithmik" mit der ISBN 3827410924 gemeint? --MartinThoma 15:15, 9. Feb. 2012 (CET)

Entweder ich habe mich gerade im Artikel getäuscht, oder jemand war sehr schnell.

Dieser Abschnitt kann archiviert werden. MartinThoma 15:41, 9. Feb. 2012 (CET)