Chomsky-Normalform

Die Chomsky-Normalform ist ein Begriff der theoretischen Informatik, der im Zusammenhang mit kontextfreien Sprachen von Interesse ist. Sie ist nach dem US-Linguisten Noam Chomsky benannt und beschreibt eine Normalform der kontextfreien Grammatiken, also eine Teilmenge der kontextfreien Grammatiken, die gegenüber der Menge der allgemeinen kontextfreien Grammatiken nichts an Ausdrucksstärke einbüßt. Die Bedeutung der Chomsky-Normalform liegt in der sehr einfachen Struktur der Produktionenen, die in effiziente Algorithmen wie dem CYK-Algorithmus eingesetzt wird.

Eine weitere Normalform für kontextfreie Grammatiken ist die Greibach-Normalform, eine der Chomsky-Normalform ähnliche Normalform für kontextsensitive Grammatiken ist die Kuroda-Normalform.

Inhaltsverzeichnis

1 Definition
2 Eigenschaften
3 Umwandlung einer Grammatik in Chomsky-Normalform

Definition

Eine formale Grammatik ist in Chomsky-Normalform (kurz CNF), wenn alle Produktionenen die folgende Form haben:

wobei AA, BB und CC Variablen sind und aa ein Terminalsymbol ist.

Eigenschaften

Jede Grammatik in Chomsky-Normalform ist eine kontextfreie Grammatik.
Zu jeder kontextfreien Grammatik mit existiert eine Grammatik in Chomsky-Normalform, die die gleiche Sprache erzeugt, d.h. . wird dann auch eine Chomsky-Normalform der kontextfreien Grammatik genannt.

Umwandlung einer Grammatik in Chomsky-Normalform

Sei

eine kontextfreie Grammatik mit

. Eine Chomsky-Normalform

von

kann so konstruiert werden:

Für jeden Kreis der Form in der Produktionenmenge ersetze man alle Variablen durch eine einzige Variable. Entferne außerdem Produktionen mit gleicher linker und rechter Seite.
Nun lässt sich die Menge der Variablen so zu sortieren, dass für alle Produktionen gilt: . Mit steigendem ii wird sukzessive jede Produktion in folgender Form behandelt: Ersetze die Produktion durch die Produktionenmenge , wobei alle rechten Seiten von Produktionen mit der linken Seite durchläuft.
Alle in auftretenden Terminalsymbole aa werden jeweils durch eine neue Variable ersetzt, und für jedes Terminalsymbol aa wird die neue Produktionen eingeführt.
Nun existieren nur noch Produktionen der Form und mit . Jede Produktion der zweiten Art mit erstetzt man durch folgende neuen Produktionen: , für alle und . Dabei seien neue Variablen.