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

Definition

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

• ${\displaystyle A\rightarrow BC}$
• ${\displaystyle A\rightarrow a}$
• ${\displaystyle S\rightarrow \varepsilon }$

wobei ${\displaystyle A}$, ${\displaystyle B}$ und ${\displaystyle C}$ Nichtterminalsymbole aus ${\displaystyle V}$ sind und ${\displaystyle a}$ ein Terminalsymbol aus ${\displaystyle \Sigma }$ ist. ${\displaystyle S}$ ist das Startsymbol und ${\displaystyle \varepsilon }$ das leere Wort. Wenn die Produktion ${\displaystyle S\rightarrow \varepsilon }$ zur Grammatik gehört, dann darf ${\displaystyle S}$ 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 ${\displaystyle G=(V,\Sigma ,P,S)}$ vor, so lässt sich daraus schrittweise eine Grammatik ${\displaystyle G'}$ in Chomsky-Normalform generieren, die dieselbe Sprache erzeugt:

Ausnahme ${\displaystyle S\rightarrow \varepsilon }$ behandeln

Enthält die Grammatik ${\displaystyle G}$ die Regel ${\displaystyle S\rightarrow \varepsilon }$, wird ein neues Startsymbol ${\displaystyle S'}$ für ${\displaystyle G'}$ eingeführt. Anschließend erhält die neue Grammatik die Regeln ${\displaystyle S'\rightarrow \varepsilon }$ und ${\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 ${\displaystyle a}$ wird ein Nichtterminalsymbol ${\displaystyle X_{a}}$ zugeordnet. Auf der rechten Seite jeder Produktion werden sämtliche Terminalsymbole ${\displaystyle a}$ durch das entsprechende Nichtterminalsymbol ${\displaystyle X_{a}}$ ersetzt. Abschließend werden alle Produktionen ${\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 ${\displaystyle AB}$ durch ein neues Nichtterminal ${\displaystyle Y_{AB}}$ ersetzt. Die Produktion ${\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 ${\displaystyle A\rightarrow \varepsilon }$, außer ${\displaystyle S'\rightarrow \varepsilon }$ (falls vorhanden).

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

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

Aus ${\displaystyle C\rightarrow AB}$ wird also:

${\displaystyle C\rightarrow B}$

${\displaystyle C\rightarrow AB}$

Kettenregeln (Produktionen der Form A→B) entfernen

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

Beispiel

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

• ${\displaystyle S\rightarrow ASA|aB}$
• ${\displaystyle A\rightarrow B|S}$
• ${\displaystyle B\rightarrow b|\varepsilon }$

in Chomsky-Normalform zu bringen.  

1. Neue Startvariable hinzufügen

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

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

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

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

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

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

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

  danach ${\displaystyle A\rightarrow S}$

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

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

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

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

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

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

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

  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