Chomsky-Normalform

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:

  • A \rightarrow BC
  • A \rightarrow a
  • S \rightarrow \varepsilon

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 S \rightarrow \varepsilon 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 S\rightarrow\varepsilon behandeln
Enthält die Grammatik G die Regel S\rightarrow\varepsilon, wird ein neues Startsymbol S' für G' eingeführt. Anschließend erhält die neue Grammatik die Regeln S'\rightarrow\varepsilon und S'\rightarrow S. 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 X_a \rightarrow a 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 Y_{AB} \rightarrow AB wird zur Grammatik hinzugefügt. Dies wiederholt man solange, bis keine Produktion mit mehr als zwei Nichtterminalen mehr vorkommt.
ε-Produktionen entfernen
Streiche die Regeln A \rightarrow \varepsilon, außer S'\rightarrow \varepsilon (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 C \rightarrow AB wird dann beispielsweise um die Regel C\rightarrow B ergänzt.
Kettenregeln (Produktionen der Form A→B) entfernen
Wenn man eine Kettenregel, d. h. eine Produktion der Form A \rightarrow B, entfernt, fügt man für jede vorhandene Produktion der Form B \rightarrow w eine neue Produktion A \rightarrow w 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


Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Chomsky Normalform — Die Chomsky Normalform (Abk.: CNF) ist eine kontextfreie Grammatik mit einer besonders einfachen Struktur der Produktionen. Sie ist ein Begriff aus der Theorie der formalen Sprachen, einem Teilbereich der Theoretischen Informatik. Sie ist nach… …   Deutsch Wikipedia

  • Chomsky — ist der Name folgender Personen: Aviva Chomsky (* 1957), US amerikanische Historikerin, Tochter von Carol und Noam Chomsky Carol Chomsky (1930–2008), US amerikanische Linguistin Marvin J. Chomsky (* 1929), US amerikanischer Filmregisseur und… …   Deutsch Wikipedia

  • Normalform — Unter einer Normalform (auch kanonische Form) versteht man eine Darstellung mit bestimmten vorgegebenen Eigenschaften. Mitunter ist die Darstellung eindeutig. Formal ist eine Normalform ein letztes Element in einer Kette von einer wohlfundierten… …   Deutsch Wikipedia

  • Greibach-Normalform — Die Greibach Normalform ist ein Begriff der theoretischen Informatik, der im Zusammenhang mit kontextfreien Sprachen von Interesse ist. Sie ist nach der US Informatikerin Sheila A. Greibach benannt und beschreibt eine Normalform der kontextfreien …   Deutsch Wikipedia

  • Kuroda-Normalform — Die Kuroda Normalform ist ein Begriff der Theoretischen Informatik, der im Zusammenhang mit kontextsensitiven Sprachen von Interesse ist. Sie ist nach dem Linguisten Sige Yuki Kuroda benannt und beschreibt eine Normalform der kontextsensitiven… …   Deutsch Wikipedia

  • Backus-Normalform — Die Backus Naur Form oder Backus Normalform, kurz BNF, ist eine kompakte formale Metasprache zur Darstellung kontextfreier Grammatiken (Typ 2 Grammatiken in der Chomsky Hierarchie). Hierzu zählt die Syntax gängiger höherer Programmiersprachen.… …   Deutsch Wikipedia

  • CNF — Die Chomsky Normalform (Abk.: CNF) ist eine kontextfreie Grammatik mit einer besonders einfachen Struktur der Produktionen. Sie ist ein Begriff aus der Theorie der formalen Sprachen, einem Teilbereich der Theoretischen Informatik. Sie ist nach… …   Deutsch Wikipedia

  • Chomskynormalform — Die Chomsky Normalform (Abk.: CNF) ist eine kontextfreie Grammatik mit einer besonders einfachen Struktur der Produktionen. Sie ist ein Begriff aus der Theorie der formalen Sprachen, einem Teilbereich der Theoretischen Informatik. Sie ist nach… …   Deutsch Wikipedia

  • Greibachnormalform — Die Greibach Normalform ist ein Begriff der theoretischen Informatik, der im Zusammenhang mit kontextfreien Sprachen von Interesse ist. Sie ist nach der US Informatikerin Sheila A. Greibach benannt und beschreibt eine Normalform der kontextfreien …   Deutsch Wikipedia

  • Kanonische Form — Unter einer Normalform versteht man eine Darstellung, die bestimmte vorgegebene Eigenschaften hat. Insbesondere bezeichnet Normalform in der Mathematik eine Darstellung eines Objektes, die bestimmte vorgegebene Eigenschaften hat und für alle… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”