Diskussion:Chomsky-Normalform

Kontextfreie Sprache

Frage: Warum darf das $S->epsilon$ nicht auf der rechten Seite stehen? Wir befinden uns doch innerhalb der kontextfreien Grammatik und nicht in der kontextsensitiven. Der Chomsky Hierarchie nach darf bei der regulären und bei der kontextfreien Grammatik auch das $S$ auf der rechten Seite vorkommen. Handelt es sich hierbei um eine Definition der Chomsky Normalform? (nicht signierter Beitrag von 37.4.26.143 (Diskussion) 12:39, 28. Okt. 2013 (CET))

Bitte was?

Bitte was???? --HansG 18:53, 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:58, 20. Feb 2004 (CET)

S -> epsilon

Wenn mich nicht alles täuscht, fehlt bei der Definition S -> epsilon. sieht das noch jemand so? Gast 14:15, 20. Feb 2006

Ja stimmt, momentan könnten nur Sprachen erzeugt werden, die das leere Wort nicht enthalten. Gruß Wasseralm 17:42, 20. Feb 2006 (CET)

Erledigt. Die fehlende Produktregel wurde aufgenommen. --Squizzz 16:01, 6. Sep 2006 (CEST)

Kann es sein, dass die Regel S-> epsilon als aller erstes aufgelöst werden muss? Steht zumindest so in dem Buch von Uwe Schöning das wir als Skript und Grundlage unserer Info3 Veranstaltung verwenden.

Abschnitt „Konstruktion einer Chomsky-Normalform“

Fehlerhafte Ableitungsregeln

Wenn eine Regel schon die Form A -> a hat, sollte keine neue Ableitungsregel für das Nichtterminal a auf der rechten Seite eingeführt werden... Führt man den Algorithmus strikt so aus wie er hier beschrieben wird, kommt man sonst auf kein Ergebnis! (Vorstehender nicht signierter Beitrag stammt von Stephan- (Diskussion • Beiträge) 14:38, 19. Sep 2006)

Das stimmt nicht. Betrachtet man die von dir angeführte Produktion $A\rightarrow a$, dann wird diese durch $A\rightarrow X_{a}$. ersetzt und den Produktionen mit $X_{a}\rightarrow a$ eine weitere hinzugefügt. Im letzten Schritt wird dann $X_{a}\rightarrow a$ wieder durch $A\rightarrow a$ ersetzt und die Produktion $A\rightarrow X_{a}$ aus der Menge der Produktionen entfernt. --Squizzz 15:36, 19. Sep 2006 (CEST)

Im letzten Schritt wird aber auch erwaehnt das w ein bel. Wort aus nichtterminalen ist. Somit waere dieses zuruecktauschen falsch. Versteh ich da was falsch?--92.75.109.142 15:56, 16. Jan. 2011 (CET)

Stimmt. Das Zurücktauschen muss auch möglich sein, wenn w ein Terminalsymbol ist. Jetzt sollte es stimmen. --Zahnradzacken 22:42, 16. Jan. 2011 (CET)

Anderer Fehler der Ableitungsregeln

Wenn ich eine Regel der Form $A\rightarrow \epsilon$ habe, dann wird sie durch den Algorithmus nicht verändert. Sie ist aber keine gültige Regel der Normalform. Es fehlt ein Schritt: Für alle Regeln der Form $A\rightarrow \epsilon$ ändere Regeln der Form $B\rightarrow \cdots A\cdots$ in $B\rightarrow \cdots \,\cdots$

Kritik vom 15. Februar 2007

Die folgende Kritik wurde im Artikel hinterlassen:

Das ist falsch. Betrachte:

$A\rightarrow a$,

$S\rightarrow A$,

$S\rightarrow BB$,

$B\rightarrow b$,

$A\rightarrow B$.

Nach Durchführung obiger Anweisung (Satz 2 kommt nicht zur Anwendung, da A nicht zu einer anderen Variablen C ableitet) bleibt

$B\rightarrow a$,

$S\rightarrow B$,

$S\rightarrow BB$,

$B\rightarrow b$

und jetzt kann man aus S das Wort aa ableiten, was vorher nicht möglich war.

Erstens: Bitte solche Sachen incht in den Artikel, sondern auf die Diskussionsseite schreiben. Zweitens: du wendest Schritt 3 nicht korrekt an. Bevor du $A\rightarrow B$ löscht, musst du die Produktion $S\rightarrow A$ klonen und dann $A$ durch $B$ ersetzen. Bei korrekter Anwendung erhältst du dann

$A\rightarrow a$,

$S\rightarrow A$,

$S\rightarrow B$,

$S\rightarrow BB$,

$B\rightarrow b$.

--Stefan Birkner 23:52, 15. Feb. 2007 (CET)

Das stimmt so nicht! Im Artikel heißt es "Gibt es zu einer Produktion der Form $A\rightarrow B$ ein weitere Produktion der Form $A\rightarrow C$, dann erzeugt man von allen anderen Produktionen in denen $A$ auf der rechten Seite vorkommt eine Kopie". In meinem Beispiel gibt es aber neben $A\rightarrow B$ keine weitere Kettenregel mit A auf der linken Seite. Also wird Satz 2 von Schritt 3 nicht angewandt!

Und was ist mit der Produktion $A\rightarrow a$? Okay ist ein Terminalsymbol und ich mache noch eine Ergänzung. --Stefan Birkner 02:01, 16. Feb. 2007 (CET)

Auch die neue Formulierung ist falsch. Betrachte:

$S\rightarrow AA$,

$A\rightarrow a$,

$B\rightarrow b$,

$A\rightarrow B$.

Nach Anwendung der Vorschrift ergibt sich:

$S\rightarrow AA$,

$S\rightarrow BB$,

$A\rightarrow a$,

$B\rightarrow b$.

Mit diesen Produktionen ist es nicht mehr möglich, aus S das Wort ab abzuleiten, was vorher ging.

-- 12:38, 16. Feb. 2007 (CET)

Regelteil hinzufügen? (vom 26. November 2007)

Ich habe auch gerade die Wiki-Seite benutzt um etwas für die Uni im Bereich Theoretische Informatik zu tun und da ist mir ein fehlender Hinweis aufgefallen:

:Streiche die Regeln $A\rightarrow \epsilon$.
:Falls Regeln der Art $A\rightarrow BC$ mit $C\rightarrow \epsilon$ existieren, ersetze sie durch $A\rightarrow B$.

Falls es mehrere Regeln gibt, die von A wegführen, aber eine davon $A\rightarrow \epsilon$ ist, dann muss $A\rightarrow BC$ mit $C\rightarrow \epsilon$ nicht durch $A\rightarrow B$ ersetzt werden, sondern eine solche Regel hinzugefügt werden. Ich habe es nicht direkt eingepflegt, weil ich nicht weiß, ob ich wirklich richtig liege und niemanden, der sich auf den Artikel verlässt, verunsichern will. Kann das mal jemand prüfen und ggf. einfügen? --Timo.Scheffler 14:27, 26. Nov. 2007 (CET)

Hab das jetzt mal korrigiert. --Thexudox (Diskussion) 15:39, 23. Jul. 2013 (CEST)

Regel S -> epsilon?

nach meiner Kenntnis gibt es eine alternative Definition, nach auch eine Regel der Form S -> epsilon nicht zu einer Chomsky-Normalform gehört.

kontextfrei / kontextsensitiv

die Bildungsvorschrift für CNF ist wirklich gruslig formuliert =/ ich werde innerhalb der nächsten Woche einen alternativen Vorschlag liefern und den zur Abstimmung aufstellen. --TheGuiTarJokeR 15:59, 25. Jan. 2010 (CET)

Zunächstmal müsste die Vorschrift auch korrigiert werden, denn sie berücksichtigt nicht in vollem Umfang, dass die Definition in diesem Artikel $S\rightarrow \varepsilon$ erlaubt. Bin auf den Vorschlag gespannt --Zahnradzacken 17:38, 26. Jan. 2010 (CET)

Bevor das mit der Einleitung ein Hin und Her wird, sollten wir uns hier einigen: Kontextfrei ist in gewisser Weise spezieller als kontextsensitiv, aber es gibt kontextfreie Grammatiken, die nicht kontextsensitiv sind. Beispiel: $S\rightarrow AB\quad A\rightarrow a\quad B\rightarrow \varepsilon$. Solche Regeln sind bei kontextfreien Grammatiken möglich, bei kontextsensitiven nicht. Es gibt aber diverse dazu äquivalente kontextfreie Grammatiken, die die gleiche Sprache erzeugen aber auch kontextsensitiv sind. Eine davon ist immer die Chomsky-Normalform zu der Grammatik: Eine CNF ist eine Normalform zu einer kontextfreien Grammatik, die aber auch kontextsensitiv ist. --Zahnradzacken 21:31, 25. Jan. 2010 (CET)

Inzwischen wurde dein Revert gesichtet, deshalb will ich nicht ebenfalls reverten. Schlag statt dessen doch bitte vor, ob und wie du die Information im Artikel einbauen würdest. --Zahnradzacken 17:38, 26. Jan. 2010 (CET)

hm, grammatiken die kontextfrei aber nicht kontextsensitiv sind, sind mir persönlich nicht bekannt. deine beispiele sind übrigens kontextsensitiv, da um jede Produktion ein sogenannter epsilonkontext existiert... ich weiß aber nicht wie tief du in der materie drinsteckst. ich bin da zugegebenermaßen noch grün hinter den ohren und dementsprechend schnell verwirrt, wenn die diskussion den mir bekannten informationsrahmen sprengt :)
aber bei den bildungsregeln einer CNF bin ich recht zuversichtlich, dass ich den artikel etwas nachvollziehbarer gestalten kann, wenn ich die nötige zeit finde, alles auszuformulieren (nicht signierter Beitrag von TheGuiTarJokeR (Diskussion | Beiträge) 18:12, 26. Jan. 2010 (CET))

Schade, zu Epsilonkontext gibt es keine Google-Treffer. Kannst du mir das erklären? Nach der Definition von kontextsensitiven Grammatiken hier in der Wikipedia sind meine Beispiele von oben aber nicht kontextsensitiv. Auch hier auf Folie 6 heißt es, dass nur nicht-verkürzende CFGs auch kontextsensitiv sind. Ich habe auch den Eindruck, dass diese Definition etabliert ist.--Zahnradzacken 19:30, 26. Jan. 2010 (CET)

Die definition von kontextsensitiven Grammatiken hier in Wikipedia sagt, genau wie der Foliensatz, den du referenziert, nur aus, dass die Produktionen nicht verkürzend sein sollen, also für $\alpha \rightarrow \beta$ muss gelten $|\alpha |<=|\beta |$ der "kontext" dabei kann durchaus auch leer sein, also $\varepsilon$. der genaue begriff dafür fällt mir leider nicht ein. die einzige Regel die dieser Bedingung widerspricht in deinem Beispiel ist $\quad B\rightarrow \varepsilon$ aber epsilonproduktionen sind nicht an sich weder in kontextfreien noch in kontextsensitiven grammatiken per definition wirklich erlaubt, siehe dazu hier auf Folie 5 weiterhin ist die Menge der kontextfreien Grammatiken eine echte Teilmenge der Menge der kontextsensitiven Grammatiken, siehe dazu hier auf Folie 8 und 9, daher muss gelten, wenn eine grammatik kontextfrei ist, dann ist sie auch kontextsensitiv, und wenn eine Grammatik nicht kontextsensitiv ist, dann ist sie auch nicht kontextfrei. nicht $\varepsilon$-treue Grammatiken können also eventuell die gleiche Sprache wie kontextfreie oder kontextsensitive Grammatiken erzeugen, aber da sie verkürzend sind, fallen sie nach Definition der Chomsky-hierarchie in die allgemeinen grammatiken, sind also weder kontextfrei noch kontextsensitiv. dieser teil der definition wird aber im normalfall nicht so wirklich ernst genommen, weil das umformen einer Grammatik ein eine $\varepsilon$-treue Grammatik eigentlich trivial ist.--TheGuiTarJokeR 08:03, 27. Jan. 2010 (CET)

Folie 5 sagt, dass man für kontext-sensitive Grammatiken $S\rightarrow \varepsilon$ erlaubt, wobei S das Startsymbol ist und es dann auf keiner rechten Seite stehen darf. Diese Ausnahmeregel ist auch in der Wikipedia-Version enthalten, mein Beispiel wird aber nicht davon abgedeckt und verletzt damit das Kriterium, nicht verkürzen zu dürfen, ist also nicht kontextsensitiv. Kontextfreie Grammatiken dürfen verkürzen, das steht so auf Folie 3, denn dort steht, dass Typ 2 die Form $X\rightarrow x$ hat, wobei $x\in (N\cup T)^{*}$, x darf also auch $\varepsilon$ sein.

Was du auf Folie 8 siehst, ist die Teilmengenbeziehung der Sprachen. Da es zu jeder kontextfreien Grammatik, die nicht kontextsensitiv ist, auch eine sprachäquivalente kontextsensitive Grammatik gibt, ist das kein Widerspruch. Auf Folie 10 steht dann auch, dass die Beweise der Inklusionen trivial seien, da auch die Grammatiken diese Inklusionsbeziehung hätten, eben bis auf $KF\subset KS$, diese Sprachinklusion benötigt einen eigenen Beweis.

Zugegeben, das ist womöglich verwirrend und es war mir selbst bis vor wenigen Tagen nicht klar. Umso wichtiger ist es mir seither, das möglichst klar abzugrenzen. Es ist letztlich natürlich Definitionssache, wie auch die CNF, denn der englische Artikel enthält auch eine zweite Definition der CNF, die gar keine $\varepsilon$-Produktionen zulässt. Ich glaube aber nicht, dass sich auch für die Grammatik-Typen mehrere Definitionen etabliert haben. Ich hoffe, du kannst meine Argumente nachvollziehen, und falls nicht, dass du weiterhin widersprichst :)

--Zahnradzacken 12:56, 27. Jan. 2010 (CET)

hm, nach deiner argumentation wären alle Grammatiken, die verkürzend und kontextfrei sind, nicht kontextsensitiv. ich gebe zu dass das irgendwo sinn macht aber ich werd wohl meinen Professor noch mal damit belappen bevor ich das endgültig glaube ;)--TheGuiTarJokeR 09:58, 28. Jan. 2010 (CET)

Gerne, bin auf die Antwort gespannt. In der Zwischenzeit aber noch ein Argument für meine Auslegung (man kann nie sicher genug gehen): '22.4 Beispiel' auf Folie 157/158, auf Folie 158 ist die Rede von einer kontextfreien Grammatik mit nicht kontextsensitiven Regeln. Das deutet darauf hin, dass ich die bisherigen Informationen richtig gedeutet habe, aber nicht, dass es nicht doch andere Definitionen gibt --Zahnradzacken 12:22, 28. Jan. 2010 (CET)

hm, das les ich so genau da jetzt nicht raus. welche stelle meinst du? --TheGuiTarJokeR 13:37, 28. Jan. 2010 (CET)

Hoppla. Dann muss eben Folie 157 herhalten. Dort heißt es, dass keine weiteren Beziehungen zwischen den Grammatiken bestehen, als die in 22.1 und 22.2, also ist jede Typ3-Grammatik auch Typ2 und jede Typ1-Grammatik auch Typ0, aber für Typ2 und Typ1 gilt keine solche Beziehung. --Zahnradzacken 23:10, 28. Jan. 2010 (CET)

stimmt, du hast recht, da stehts. "Kontextfreie Grammatiken müssen daher nicht $\lambda$-treu und daher i. Allg. nicht kontextsensitiv sein"

mein Prof gibt dir auch recht :> er meinte aber das wär einer der in der informatik am meisten umzankten streitpunkte. --TheGuiTarJokeR 03:42, 29. Jan. 2010 (CET)

epsilon-Regeln streichen

"Gab es vorher genau eine Produktion mit A auf der linken Seite, so streiche das A überall auf den rechten Seiten der Produktionen." Die Grammatik darf keine Regeln mit einer leeren rechten Seite haben, aber z.B. im Falle von B -> A A würde durch das einfache streichen eine solche Regel entstehen. 91.35.51.144 16:21, 3. Nov. 2013 (CET)