CNF


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 dem US-Linguisten Noam Chomsky benannt und kommt beim CYK-Algorithmus zum Einsatz.

Zu jeder kontextfreien Sprache gibt es eine 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 ist in Chomsky-Normalform, wenn jede Produktion eine der folgenden Formen hat:

  • A \rightarrow BC
  • A \rightarrow a
  • S \rightarrow \epsilon

wobei A, B und C Nichtterminalsymbole sind und a ein Terminalsymbol ist. S ist das Startsymbol und ε das leere Wort. Wenn die Produktion S \rightarrow \epsilon 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 vor, so lässt sich daraus schrittweise eine Chomsky-Normalform generieren, die dieselbe Sprache erzeugt:

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 \epsilon.
Falls Regeln der Art A \rightarrow BC mit C \rightarrow \epsilon existieren, ersetze sie durch A \rightarrow B.
Hierbei muss man aufpassen, dass man das Resultat der Abbildungen nicht inhaltlich verändert. Beispiel: eine Abbildung der Startvariable S auf eine oder mehrere Variablen die wiederum auf ε abgebildet werden, sprich die Erzeugung des leeren Wortes, muss auch bei der Grammatik in Chomsky-Normalform möglich sein. S bildet sozusagen eine Ausnahme der obigen Definition, da es die Abbildung S \rightarrow \epsilon geben darf.
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 ein beliebiges Wort aus Nichtterminalen.

Quellen

  • Grzegorz Rozenberg, Arto Salomaa: Handbook of Formal Languages. Volume 1. Word, Language, Grammar. Springer-Verlag, 1997, ISBN 3-540-60420-0, S. 124–125

Weblinks


Wikimedia Foundation.

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

  • CNF — Saltar a navegación, búsqueda CNF puede referirse a: Aeropuerto Internacional Tancredo Neves, en la ciudad de Belo Horizonte, Brasil (Código de Aeropuerto IATA); Campeonato Nacional de Fútbol de Cuba Obtenido de CNF Categoría:… …   Wikipedia Español

  • CNF — is a three letter acronym, and may refer to: Cornell NanoScale Facility Canadian Neutron Facility at the Canadian Neutron Beam Centre Canadian Nurses Foundation Carbon nanofibers Caribbean National Forest Cameroons National Federation Chomsky… …   Wikipedia

  • CNF — Abreviatura de la Canadian Nurses Foundation. Diccionario Mosby Medicina, Enfermería y Ciencias de la Salud, Ediciones Hancourt, S.A. 1999 …   Diccionario médico

  • CNF PT — Cnf Tr I (Business » NYSE Symbols) …   Abbreviations dictionary

  • .cnf — cnf,   Erweiterung für eine Datei, die Konfigurationsinformationen für Hard oder Software enthält …   Universal-Lexikon

  • CNF — CNF,   Abkürzung für Comité National Français …   Universal-Lexikon

  • CNF — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom.   Sigles d’une seule lettre   Sigles de deux lettres > Sigles de trois lettres   Sigles de quatre lettres …   Wikipédia en Français

  • CNF — Conjunctive Normal Form (Computing » General) * Chomsky Normal Form (Governmental » Transportation) * Colville National Forest (Governmental) * Compressed Natural Fuel (Business » International Business) * Configuration printer setup file… …   Abbreviations dictionary

  • CNF — chronic nodular fibrositis; congenital nephrotic syndrome of the Finnish [type]; conjunctive normal form system [Boolean logic]; cytotoxic necrotizing factor …   Medical dictionary

  • CNF — • CoNFiguration (file) • Cold Nuclear Fusion (aus sci.physics.fusion) • Cornell Nanofabrication Facility s. NNUN • Belo Horizonte Confins Airport, Brazil internationale Flughafen Kennung …   Acronyms