Hi,
habe die Chomsky-Normalform durchgearbeitet und einen kleinen Unterschied zu der Version aus Wikipedia gesehen. Bei der Wikipedia Version wird noch explizit jede Produktion der Form X -> € (epsilon) entfernt. Im Skript von Prof. Otto ist das nicht der Fall.
Natürlich ist das ja einfach in dem ich gerade X->€ entferne und diese durch eine geeignet Form ersetze, aber ist das überhaupt korrekt und so gewollt, da es ja nicht in dem Skript steht.
Beispiel für L={a^n*b^n | n € N} \ {€} also für n > 0
Die Produktion ist standardmäßig X > aXb und X->€.
Aber da das leere Wort nicht mehr da ist, muss natürlich X->€ weg.
Da ich die Chomsky-Normalform aus L bilden sollte, muss irgendwie das epsilon, was aber laut Skript nicht nötig ist, ist denn überhaupt die PRoduktion X->€ Chomsky-konform?
Ich habe diese durch X->AB ersetzt, wobei A->a und B->b verweist. Auf jeden Fall kann man leicht das epsilon entfernen ohne die Sprache zu verändern. Ist das aber nun so korrekt (laut den Veranstaltern)?
Chomsky-Normalform
eine epsilon-produktion hat in einer chomsky-nf glaub nix zu suchen, (bis auf s -> e ) aber alle nichtharmlosen e-produktionen lassen sich ja ohne probleme eliminieren (das müsste auch im skript stehn)
ich weiß gar nicht ob der prof. otto per definition nichtharmlose epsilon-produktionen überhaupt zugelassen hat für typ2-grammatik
ich weiß gar nicht ob der prof. otto per definition nichtharmlose epsilon-produktionen überhaupt zugelassen hat für typ2-grammatik
We can do this the hard way or my way ...which is basically the same thing!
Richtig, im Skript ist die Chromsky-Normalform definiert als Typ 2 Grammatik ohne \(\epsilon\) Produktion die nur Produktionen vom Typ X \(\to\) YZ und X \(\to\) a enthält (Definition 3.3.1).habe die Chomsky-Normalform durchgearbeitet und einen kleinen Unterschied zu der Version aus Wikipedia gesehen. Bei der Wikipedia Version wird noch explizit jede Produktion der Form X -> € (epsilon) entfernt. Im Skript von Prof. Otto ist das nicht der Fall.
Außerdem sagt Satz 3.3.2 aus, dass man jede Typ 2 Grammatik die nur harmlose \(\epsilon\) Produktionen enthält umformen kann in die Chromsky-Normalform.
Damit ist klar und sauber gesagt, von welchen Grammatiken wir Chromsky-Normalformen bauen können.
Jetzt kann man natürlich Lemma 3.2.4 benutzten um alle möglichen Typ 2 Grammatiken in eine Chromsky-Normalform zu bringen.
Ja sind zugelassen aber selbst wenn nicht wäre das relativ wurscht, da Du mit obigem Lemma evtl. Grammatiken ja einfach umformen kannst.ich weiß gar nicht ob der prof. otto per definition nichtharmlose epsilon-produktionen überhaupt zugelassen hat für typ2-grammatik