Chomsky Normalform bilden?
Ich habe große Probleme bei der Chomsky Normalform.
Im ersten Schritt soll man ja die ε-Übergänge entfernen. Ich bin mir in dem Beispiel nicht sicher wie ich das machen soll und wie ich mit D verfahren soll. Aus D kann man ja nur ε ableiten und es kommt ja nur bei A zum Einsatz, bei welchem man 01 ableiten kann. Das ε ist ja dabei total irrelevant. Daher die Frage ob man das D nicht eigentlich ganz entfernen könnte.
1 Antwort
Man muss eigentlich im ersten Schritt nicht produzierende und nicht erreichbare Variabeln entfernen. Danach wird jedes Terminal, was auf einer rechten Regelseite auftaucht durch eine zusätzliche Variable ersetzt. Zum Beispiel S -> A1 wird zu S -> AW_1 und W_1 -> 1.
Danach trimmt man die rechten Regelseiten auf höchstens Länge 2 herunter und benutzt dabei wenn nötig (mehrere) Hilfsvariablen. Zum Beispiel S -> CW_aC wird zu S -> CS_1 und S_1 -> W_aC.
Dann werden jetzt die Epsilon-Regeln entfernt. Dabei muss man alle Variabeln betrachten, die zu Epsilon werden können (auch durch mehrere Schritte). Hier kann man dann D ganz entfernen, da es keine Ableitung mehr hat.
danach müssen noch einheitsregeln Entfernt werden. (X -> Y) und wenn Epsilon in der Sprache enthalten ist das noch hinzufügen aber das ist hier glaube ich nicht der Fall.