- Chomsky-Normalform
-
Die Chomsky-Normalform (Abk.: CNF) ist in der theoretischen Informatik eine Normalform für kontextfreie Grammatiken. Sie ist nach dem Linguisten Noam Chomsky benannt und kommt beim CYK-Algorithmus zum Einsatz. Eine kontextfreie Grammatik in Chomsky-Normalform hat eine einfache Struktur der Produktionsregeln und erfüllt auch die Eigenschaften kontextsensitiver Grammatiken.
Zu jeder kontextfreien Sprache gibt es eine Grammatik in Chomsky-Normalform. Deshalb kann aus jeder kontextfreien Grammatik G eine Chomsky-Normalform GCNF konstruiert werden, die dieselbe Sprache erzeugt. Die Grammatik GCNF wird dann auch eine Chomsky-Normalform der kontextfreien Grammatik G genannt.
Eine Erweiterung der Chomsky-Normalform auf kontextsensitive Grammatiken stellt die Kuroda-Normalform dar.
Inhaltsverzeichnis
Definition
Eine formale Grammatik G = (V,Σ,P,S) ist in Chomsky-Normalform, wenn jede Produktion aus P eine der folgenden Formen hat:
wobei A, B und C Nichtterminalsymbole aus V sind und a ein Terminalsymbol aus Σ ist. S ist das Startsymbol und ε das leere Wort. Wenn die Produktion
zur Grammatik gehört, dann darf S nicht auf der rechten Seite einer Produktion stehen.
Lässt man bei der ersten Produktion auf der rechten Seite beliebig viele anstatt zwei Nichtterminalsymbole zu, so spricht man von einer schwachen Chomsky-Normalform.
Konstruktion einer Chomsky-Normalform
Liegt eine kontextfreie Grammatik G = (V,Σ,P,S) vor, so lässt sich daraus schrittweise eine Grammatik G' in Chomsky-Normalform generieren, die dieselbe Sprache erzeugt:
- Ausnahme
behandeln
- Enthält die Grammatik G die Regel
, wird ein neues Startsymbol S' für G' eingeführt. Anschließend erhält die neue Grammatik die Regeln
und
. Damit ist sichergestellt, dass die Grammatik weiterhin das leere Wort ermöglicht, zugleich das Startsymbol aber auf keiner rechten Seite vorkommt.
- Eine schwache Chomsky-Normalform erzeugen
- Jedem Terminalsymbol a wird ein Nichtterminalsymbol Xa zugeordnet. Auf der rechten Seite jeder Produktion werden sämtliche Terminalsymbole a durch das entsprechende Nichtterminalsymbol Xa ersetzt. Abschließend werden alle Produktionen
der Grammatik hinzugefügt.
- Rechte Seiten mit mehr als zwei Nichtterminalen ersetzen
- Sind auf der rechten Seite einer Produktion mehr als zwei Nichtterminale, so werden zwei benachbarte Nichtterminale AB durch ein neues Nichtterminal YAB ersetzt. Die Produktion
wird zur Grammatik hinzugefügt. Dies wiederholt man solange, bis keine Produktion mit mehr als zwei Nichtterminalen mehr vorkommt.
- ε-Produktionen entfernen
- Streiche die Regeln
, außer
(falls vorhanden).
- Für jede Regel, die ein solches A auf der rechten Seite enthält, wird eine Regel hinzugefügt, in der das A gestrichen wurde. Die Regel
wird dann beispielsweise um die Regel
ergänzt.
- Kettenregeln (Produktionen der Form A→B) entfernen
- Wenn man eine Kettenregel, d. h. eine Produktion der Form
, entfernt, fügt man für jede vorhandene Produktion der Form
eine neue Produktion
hinzu, falls diese keine bereits entfernte Kettenregel ergibt. w ist hierbei eine beliebiges Wort; die vorangegangenen Änderungen gewährleisten aber, dass w entweder genau ein Terminalsymbol ist oder ein Wort aus höchstens zwei Nichtterminalsymbolen.
Quellen
- Grzegorz Rozenberg, Arto Salomaa: Handbook of Formal Languages. Volume 1: Word, Language, Grammar. Springer-Verlag, Berlin u. a. 1997, ISBN 3-540-60420-0, S. 124–125
Weblinks
- Programm zur Berechnung von Chomsky-Normalformen (Java-Applet)
Wikimedia Foundation.