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. Aus jeder kontextfreien Grammatik G {\displaystyle G} kann eine Grammatik G C N F {\displaystyle G_{CNF}} in Chomsky-Normalform konstruiert werden, die dieselbe Sprache erzeugt. Die Grammatik G C N F {\displaystyle G_{CNF}} wird dann auch eine Chomsky-Normalform der kontextfreien Grammatik G {\displaystyle G} 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.

Eine formale Grammatik G = ( V , Σ , P , S ) {\displaystyle G=(V,\Sigma ,P,S)} ist in Chomsky-Normalform, wenn jede Produktion aus P {\displaystyle P} eine der folgenden Formen hat:

• A → B C {\displaystyle A\rightarrow BC}
• A → a {\displaystyle A\rightarrow a}
• S → ε {\displaystyle S\rightarrow \varepsilon }

wobei A {\displaystyle A} , B {\displaystyle B} und C {\displaystyle C} Nichtterminalsymbole aus V {\displaystyle V} sind und a {\displaystyle a} ein Terminalsymbol aus Σ {\displaystyle \Sigma } ist. S {\displaystyle S} ist das Startsymbol und ε {\displaystyle \varepsilon } das leere Wort. Wenn die Produktion S → ε {\displaystyle S\rightarrow \varepsilon } zur Grammatik gehört, dann darf S {\displaystyle 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.

Liegt eine kontextfreie Grammatik G = ( V , Σ , P , S ) {\displaystyle G=(V,\Sigma ,P,S)} vor, so lässt sich daraus schrittweise eine Grammatik G ′ {\displaystyle G'} in Chomsky-Normalform generieren, die dieselbe Sprache erzeugt:

Ausnahme S → ε {\displaystyle S\rightarrow \varepsilon } behandeln

Enthält die Grammatik G {\displaystyle G} die Regel S → ε {\displaystyle S\rightarrow \varepsilon } , wird ein neues Startsymbol S ′ {\displaystyle S'} für G ′ {\displaystyle G'} eingeführt. Anschließend erhält die neue Grammatik die Regeln S ′ → ε {\displaystyle S'\rightarrow \varepsilon } und S ′ → S {\displaystyle S'\rightarrow S} . 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 a {\displaystyle a} wird ein Nichtterminalsymbol X a {\displaystyle X_{a}} zugeordnet. Auf der rechten Seite jeder Produktion werden sämtliche Terminalsymbole a {\displaystyle a} durch das entsprechende Nichtterminalsymbol X a {\displaystyle X_{a}} ersetzt. Abschließend werden alle Produktionen X a → a {\displaystyle 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 A B {\displaystyle AB} durch ein neues Nichtterminal Y A B {\displaystyle Y_{AB}} ersetzt. Die Produktion Y A B → A B {\displaystyle Y_{AB}\rightarrow AB} wird zur Grammatik hinzugefügt. Dies wiederholt man solange, bis keine Produktion mit mehr als zwei Nichtterminalen mehr vorkommt.

ε {\displaystyle \varepsilon } -Produktionen entfernen

Streiche die Regeln A → ε {\displaystyle A\rightarrow \varepsilon } , außer S ′ → ε {\displaystyle S'\rightarrow \varepsilon } (falls vorhanden).

Gab es vorher genau eine Produktion mit A {\displaystyle A} auf der linken Seite, so streiche das A {\displaystyle A} überall auf den rechten Seiten der Produktionen, denn es kann nicht zu einem Terminal abgeleitet werden.

Gab es vorher mehrere Produktionen mit A {\displaystyle A} auf der linken Seite, so füge für jede Regel, die ein solches A {\displaystyle A} auf der rechten Seite enthält, eine Regel hinzu, in der das A {\displaystyle A} gestrichen wurde, denn es muss der Fall betrachtet werden, in dem das A {\displaystyle A} als leeres Wort abgeleitet wurde oder etwa nicht. Die Regel C → A B {\displaystyle C\rightarrow AB} wird dann beispielsweise um die Regel C → B {\displaystyle C\rightarrow B} ergänzt.

Aus C → A B {\displaystyle C\rightarrow AB} wird also:

C → B {\displaystyle C\rightarrow B}

C → A B {\displaystyle C\rightarrow AB}

Kettenregeln (Produktionen der Form A→B) entfernen

Wenn man eine Kettenregel, d. h. eine Produktion der Form A → B {\displaystyle A\rightarrow B} , entfernt, fügt man für jede vorhandene Produktion der Form B → w {\displaystyle B\rightarrow w} eine neue Produktion A → w {\displaystyle A\rightarrow w} hinzu, falls diese keine bereits entfernte Kettenregel ergibt. w {\displaystyle w} ist hierbei ein beliebiges Wort; die vorangegangenen Änderungen gewährleisten aber, dass w {\displaystyle w} entweder genau ein Terminalsymbol ist oder ein Wort aus genau zwei Nichtterminalsymbolen.

Es gilt, die Grammatik über dem Alphabet Σ = { a , b } {\displaystyle \Sigma =\{a,b\}} mit den Regeln

• S → A S A | a B {\displaystyle S\rightarrow ASA|aB}
• A → B | S {\displaystyle A\rightarrow B|S}
• B → b | ε {\displaystyle B\rightarrow b|\varepsilon }

in Chomsky-Normalform zu bringen.  

1. Neue Startvariable hinzufügen

• S 0 → S {\displaystyle S_{0}\rightarrow S}
• S → A S A | a B {\displaystyle S\rightarrow ASA|aB}
• A → B | S {\displaystyle A\rightarrow B|S}
• B → b | ε {\displaystyle B\rightarrow b|\varepsilon }

  2. ε {\displaystyle \varepsilon } -Übergänge entfernen

• S 0 → S {\displaystyle S_{0}\rightarrow S}
• S → A S A | a B | a {\displaystyle S\rightarrow ASA|aB|a}
• A → B | ε | S {\displaystyle A\rightarrow B|\varepsilon |S}
• B → b {\displaystyle B\rightarrow b}

  Eine neue ε {\displaystyle \varepsilon } -Regel ist entstanden, die wiederum gleich behandelt werden muss:

• S 0 → S {\displaystyle S_{0}\rightarrow S}
• S → A S A | A S | S A | a B | a {\displaystyle S\rightarrow ASA|AS|SA|aB|a}
• A → B | S {\displaystyle A\rightarrow B|S}
• B → b {\displaystyle B\rightarrow b}

  3. Alle Einheits-Regeln entfernen. Diese sind A → B , A → S {\displaystyle A\rightarrow B,A\rightarrow S} und S 0 → S {\displaystyle S_{0}\rightarrow S} .

• S 0 → S {\displaystyle S_{0}\rightarrow S}
• S → A S A | A S | S A | a B | a {\displaystyle S\rightarrow ASA|AS|SA|aB|a}
• A → S {\displaystyle A\rightarrow S}
• B → b {\displaystyle B\rightarrow b}
• A → b {\displaystyle A\rightarrow b}

  danach A → S {\displaystyle A\rightarrow S}

• S 0 → S {\displaystyle S_{0}\rightarrow S}
• S → A S A | A S | S A | a B | a {\displaystyle S\rightarrow ASA|AS|SA|aB|a}
• A → A S A | A S | S A | a B | a | b {\displaystyle A\rightarrow ASA|AS|SA|aB|a|b}
• B → b {\displaystyle B\rightarrow b}

  und zum Schluss S 0 → S {\displaystyle S_{0}\rightarrow S}

• S 0 → A S A | A S | S A | a B | a {\displaystyle S_{0}\rightarrow ASA|AS|SA|aB|a}
• S → A S A | A S | S A | a B | a {\displaystyle S\rightarrow ASA|AS|SA|aB|a}
• A → A S A | A S | S A | a B | a | b {\displaystyle A\rightarrow ASA|AS|SA|aB|a|b}
• B → b {\displaystyle B\rightarrow b}

  4. Längere Verkettungen sind nicht erlaubt, deshalb führen wir eine zusätzliche Variable A 1 {\displaystyle A_{1}} ein und ersetzen S → A S A {\displaystyle S\rightarrow ASA} durch die Regel S → A A 1 {\displaystyle S\rightarrow AA_{1}} und A 1 → S A {\displaystyle A_{1}\rightarrow SA} :

• S 0 → A A 1 | A S | S A | a B | a {\displaystyle S_{0}\rightarrow AA_{1}|AS|SA|aB|a}
• S → A A 1 | A S | S A | a B | a {\displaystyle S\rightarrow AA_{1}|AS|SA|aB|a}
• A → A A 1 | A S | S A | a B | a | b {\displaystyle A\rightarrow AA_{1}|AS|SA|aB|a|b}
• A 1 → S A {\displaystyle A_{1}\rightarrow SA}
• B → b {\displaystyle B\rightarrow b}

  Nun bleiben nur noch die Regeln A → a B {\displaystyle A\rightarrow aB} und S → a B {\displaystyle S\rightarrow aB} . Deshalb wird eine weitere Variable X a {\displaystyle X_{a}} verwendet, die zusammen mit der Regel X a → a {\displaystyle X_{a}\rightarrow a} das Terminalsymbol a {\displaystyle a} in den genannten Regeln ersetzen kann.

• S 0 → A A 1 | A S | S A | X a B | a {\displaystyle S_{0}\rightarrow AA_{1}|AS|SA|X_{a}B|a}
• S → A A 1 | A S | S A | X a B | a {\displaystyle S\rightarrow AA_{1}|AS|SA|X_{a}B|a}
• A → A A 1 | A S | S A | X a B | a | b {\displaystyle A\rightarrow AA_{1}|AS|SA|X_{a}B|a|b}
• A 1 → S A {\displaystyle A_{1}\rightarrow SA}
• X a → a {\displaystyle X_{a}\rightarrow a}
• B → b {\displaystyle B\rightarrow b}

  Somit ist die Grammatik in Chomsky-Normalform umgewandelt.

• 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