Chomsky-Normalform

Eser
Windoof-User
Windoof-User
Beiträge: 37
Registriert: 6. Okt 2004 18:20

Chomsky-Normalform

Beitrag von Eser »

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)?

baerchen
Computerversteher
Computerversteher
Beiträge: 382
Registriert: 24. Okt 2006 15:42

Beitrag von baerchen »

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
We can do this the hard way or my way ...which is basically the same thing!

Benutzeravatar
Red*Star
Kernelcompilierer
Kernelcompilierer
Beiträge: 510
Registriert: 28. Nov 2006 19:40

Beitrag von Red*Star »

Guckst du im Skript:
Typ 2
kontextfrei

nur Produktionen von der Form X -> v.
(Seite 49)

Da steht nichts von v != epsilon.

MP1
Neuling
Neuling
Beiträge: 9
Registriert: 3. Nov 2005 09:42
Wohnort: Darmstadt

Beitrag von MP1 »

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.
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).

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.
ich weiß gar nicht ob der prof. otto per definition nichtharmlose epsilon-produktionen überhaupt zugelassen hat für typ2-grammatik
Ja sind zugelassen aber selbst wenn nicht wäre das relativ wurscht, da Du mit obigem Lemma evtl. Grammatiken ja einfach umformen kannst.

Antworten

Zurück zu „Archiv“