Next: Das Pumping Lemma (uvwxy-Theorem)
Up: Kontextfreie Sprachen (Typ 2)
Previous: Kontextfreie Sprachen (Typ 2)
Contents
Index
Subsections
Normalformen 52
Für die Normalformen müssen folgende Regeln gelten (durch Umformungen
erreichbar):
-
-Regeln entfernen (siehe ite:Entfernen epsilon Regeln(Typ2))
- Kettenregeln
entfernen
Chomsky Normalform 53
Zu jeder kontextfreien Grammatik mit
existiert eine Chomsky Normalform (CNF). Die Chomsky
Normalform liegt vor, wenn alle Regeln eine der folgenden Formen haben:
Ist
, so gilt:
Ein Algorithmus für die Umformung findet sich im Buch (vorher Kettenregeln,
und
-Regeln entfernen!)
Greifenbach Normalform 54
Zu jeder kontextfreien Grammatik mit
existiert eine Greifenbach Normalform. Diese liegt vor, wenn
alle Regeln eine der folgenden Formen haben:
Die Greifenbach Grammatik ist eine Erweiterung der regulären Grammatik,
dort wäre nur und zugelassen.
Ein Algorithmus für die Umformung findet sich im Buch.
Next: Das Pumping Lemma (uvwxy-Theorem)
Up: Kontextfreie Sprachen (Typ 2)
Previous: Kontextfreie Sprachen (Typ 2)
Contents
Index
Marco Möller 18:11:27 24.10.2005