Hauptmenü öffnen

Chomsky-Normalform

Form kontextfreier Grammatiken in der Informatik

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 eine Chomsky-Normalform konstruiert werden, die dieselbe Sprache erzeugt. Die Grammatik wird dann auch eine Chomsky-Normalform der kontextfreien Grammatik genannt.

Eine weitere Normalform für kontextfreie Grammatiken ist die Greibach-Normalform. Eine Erweiterung der Chomsky-Normalform auf kontextsensitive Grammatiken stellt die Kuroda-Normalform dar. Die Chomsky-Normalform wird auf Grund der gleichen Abkürzung leicht mit der Konjunktiven Normalform (engl. conjunctive normal form) verwechselt.

Inhaltsverzeichnis

DefinitionBearbeiten

Eine formale Grammatik   ist in Chomsky-Normalform, wenn jede Produktion aus   eine der folgenden Formen hat:

  •  
  •  
  •  

wobei  ,   und   Nichtterminalsymbole aus   sind und   ein Terminalsymbol aus   ist.   ist das Startsymbol und   das leere Wort. Wenn die Produktion   zur Grammatik gehört, dann darf   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-NormalformBearbeiten

Liegt eine kontextfreie Grammatik   vor, so lässt sich daraus schrittweise eine Grammatik   in Chomsky-Normalform generieren, die dieselbe Sprache erzeugt:

Ausnahme   behandeln
Enthält die Grammatik   die Regel  , wird ein neues Startsymbol   für   eingeführt. Anschließend erhält die neue Grammatik die Regeln   und  . Damit ist sichergestellt, dass die Grammatik weiterhin das leere Wort ermöglicht und das ursprüngliche Startsymbol weiterhin auf der rechten Seite verwendet werden kann.
Eine schwache Chomsky-Normalform erzeugen
Jedem Terminalsymbol   wird ein Nichtterminalsymbol   zugeordnet. Auf der rechten Seite jeder Produktion werden sämtliche Terminalsymbole   durch das entsprechende Nichtterminalsymbol   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   durch ein neues Nichtterminal   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).
Gab es vorher genau eine Produktion mit   auf der linken Seite, so streiche das   überall auf den rechten Seiten der Produktionen, denn es kann nicht zu einem Terminal abgeleitet werden.
Gab es vorher mehrere Produktionen mit   auf der linken Seite, so füge für jede Regel, die ein solches   auf der rechten Seite enthält, eine Regel hinzu, in der das   gestrichen wurde, denn es muss der Fall betrachtet werden in dem das   als leeres Wort abgeleitet wurde oder etwa nicht. Die Regel   wird dann beispielsweise um die Regel   ergänzt.
Aus   wird also:
 
 
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.   ist hierbei ein beliebiges Wort; die vorangegangenen Änderungen gewährleisten aber, dass   entweder genau ein Terminalsymbol ist oder ein Wort aus genau zwei Nichtterminalsymbolen.

BeispielBearbeiten

Es gilt, die Grammatik über dem Alphabet   mit den Regeln

  •  
  •  
  •  

in Chomsky Normalform zu bringen.  

1. Neue Startvariable hinzufügen

  •  
  •  
  •  
  •  

  2.  -Übergänge entfernen

  •  
  •  
  •  
  •  

  Eine neue  -Regel ist entstanden, die wiederum gleich behandelt werden muss:

  •  
  •  
  •  
  •  

  3. Alle Einheits-Regeln entfernen. Diese sind   und  .

  •  
  •  
  •  
  •  
  •  

  danach  

  •  
  •  
  •  
  •  

  und zum Schluss  

  •  
  •  
  •  
  •  

  4. Längere Verkettungen sind nicht erlaubt, deshalb führen wir eine zusätzliche Variable   ein und ersetzen   durch die Regel   und  :

  •  
  •  
  •  
  •  
  •  

  Nun bleiben nur noch die Regel   und  . Deshalb wird eine weitere Variable   verwendet die zusammen mit der Regel   das Terminalsymbol   in den genannten Regeln ersetzen kann.

  •  
  •  
  •  
  •  
  •  
  •  

  Somit ist die Grammatik in Chomsky-Normalform umgewandelt.

QuellenBearbeiten

  • 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