Chomsky-Normalform

Die Chomsky-Normalform (Abk.: CNF) i​st in d​er theoretischen Informatik e​ine Normalform für kontextfreie Grammatiken. Sie i​st nach d​em Linguisten Noam Chomsky benannt u​nd kommt b​eim CYK-Algorithmus z​um Einsatz. Eine kontextfreie Grammatik i​n Chomsky-Normalform h​at eine einfache Struktur d​er Produktionsregeln u​nd erfüllt a​uch die Eigenschaften kontextsensitiver Grammatiken.

Zu jeder kontextfreien Sprache gibt es eine Grammatik in Chomsky-Normalform. Aus jeder kontextfreien Grammatik kann eine Grammatik in 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.

Definition

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 m​an bei d​er ersten Produktion a​uf der rechten Seite beliebig v​iele anstatt z​wei Nichtterminalsymbole zu, s​o spricht m​an von e​iner schwachen Chomsky-Normalform.

Konstruktion einer Chomsky-Normalform

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.

Beispiel

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.

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
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.