Chomsky-Normalform

Bedeutung und Zweck

Die Chomsky-Normalform (CNF) ist eine Normalform für kontextfreie Grammatiken in der theoretischen Informatik. Sie bringt deren Produktionsregeln in eine besonders einfache, einheitliche Struktur und wird unter anderem beim CYK-Algorithmus verwendet. Eine Grammatik in Chomsky-Normalform erfüllt außerdem die Eigenschaften kontextsensitiver Grammatiken.

Zu jeder kontextfreien Sprache existiert eine Grammatik in Chomsky-Normalform. Aus jeder kontextfreien Grammatik G kann daher eine Grammatik G_CNF konstruiert werden, die genau dieselbe Sprache erzeugt. G_CNF wird dann als eine Chomsky-Normalform von G bezeichnet.

Andere verwandte Normalformen sind die Greibach-Normalform für kontextfreie Grammatiken und die Kuroda-Normalform als Erweiterung auf kontextsensitive Grammatiken. Die Abkürzung CNF kann leicht mit der Konjunktiven Normalform verwechselt werden, die auf Englisch ebenfalls „conjunctive normal form“ heißt.

Zulässige Produktionsregeln

Eine formale Grammatik G = (V, Σ, P, S) liegt in Chomsky-Normalform vor, wenn jede Produktion aus P genau eine der folgenden Formen besitzt:

• A → BC • A → a • S → ε

Dabei sind A, B und C Nichtterminalsymbole aus V. Nichtterminalsymbole sind Hilfssymbole, die bei einer Ableitung weiter ersetzt werden können. Das Zeichen a ist ein Terminalsymbol aus dem Alphabet Σ, also ein Zeichen des erzeugten Wortes. S bezeichnet das Startsymbol und ε das leere Wort.

Die Regel S → ε ist nur nötig, wenn die Sprache das leere Wort enthält. Kommt sie vor, darf S auf keiner rechten Seite einer Produktion stehen. Dadurch bleibt diese Regel der einzige zulässige Weg, ε zu erzeugen.

Bei A → BC stehen rechts genau zwei Nichtterminalsymbole, bei A → a genau ein Terminalsymbol. Erlaubt man statt genau zwei beliebig viele Nichtterminalsymbole auf der rechten Seite der ersten Regelart, spricht man von einer schwachen Chomsky-Normalform.

Umwandlung einer Grammatik

Eine kontextfreie Grammatik G = (V, Σ, P, S) lässt sich schrittweise in eine sprachäquivalente Grammatik G′ in Chomsky-Normalform überführen:

• Leeres Wort behandeln: Enthält G die Regel S → ε, wird ein neues Startsymbol S′ eingeführt. Man ergänzt S′ → ε und S′ → S. So kann die neue Grammatik weiterhin das leere Wort erzeugen, während das alte Startsymbol auf rechten Seiten vorkommen darf.

• Terminalsymbole in längeren rechten Seiten ersetzen: Jedem Terminalsymbol a wird ein Nichtterminalsymbol X_a zugeordnet. Terminalsymbole auf rechten Seiten werden durch die entsprechenden X_a ersetzt; zusätzlich fügt man jeweils X_a → a hinzu. Dadurch entsteht zunächst eine schwache Chomsky-Normalform.

• Lange Folgen von Nichtterminalsymbolen zerlegen: Enthält eine rechte Seite mehr als zwei Nichtterminalsymbole, werden zwei benachbarte Symbole AB durch ein neues Nichtterminal Y_AB ersetzt. Gleichzeitig kommt Y_AB → AB hinzu. Dieser Vorgang wird wiederholt, bis rechts höchstens zwei Nichtterminalsymbole stehen.

• ε-Produktionen entfernen: Regeln A → ε werden gestrichen; eine vorhandene Regel S′ → ε bleibt ausgenommen. War A zuvor die einzige linke Seite einer einzelnen Produktion und kann deshalb nicht zu einem Terminal abgeleitet werden, wird A auch aus den rechten Seiten entfernt. Gibt es mehrere Produktionen für A, müssen beide Fälle erhalten bleiben: A kann als ε verschwinden oder bestehen bleiben. Aus C → AB entstehen deshalb beispielsweise C → B und C → AB.

• Kettenregeln entfernen: Eine Kettenregel hat die Form A → B. Beim Entfernen werden für jede Produktion B → w entsprechende Produktionen A → w ergänzt, sofern dadurch keine bereits entfernte Kettenregel wieder entsteht. Nach den vorherigen Schritten ist w entweder genau ein Terminalsymbol oder eine Folge aus genau zwei Nichtterminalsymbolen.

Beispiel der Umwandlung

Gegeben ist eine Grammatik über Σ = {a, b} mit S → ASA | aB, A → B | S und B → b | ε.

Zuerst wird mit S₀ → S eine neue Startvariable eingeführt. Beim Entfernen der ε-Regel B → ε muss berücksichtigt werden, dass B in aB entfallen kann. Dadurch kommt S → a hinzu. Vorübergehend entsteht außerdem A → ε; ihre Beseitigung ergänzt für S → ASA die Varianten S → AS und S → SA. Danach gelten unter anderem S → ASA | AS | SA | aB | a, A → B | S und B → b.

Anschließend werden die Einheits- beziehungsweise Kettenregeln A → B, A → S und S₀ → S entfernt. Ihre nicht als Kettenregeln geformten Alternativen werden auf die jeweiligen linken Seiten übertragen. Damit erhalten S₀, S und A die erforderlichen Produktionen; A erhält zusätzlich A → b.

Die noch zu lange rechte Seite ASA wird nun zerlegt. Dafür wird A₁ eingeführt, wobei ASA durch AA₁ ersetzt und A₁ → SA ergänzt wird. Schließlich stehen in aB noch ein Terminal- und ein Nichtterminalsymbol nebeneinander. Man ersetzt a dort durch X_a und ergänzt X_a → a.

Die fertige Grammatik besitzt die Regeln:

• S₀ → AA₁ | AS | SA | X_aB | a • S → AA₁ | AS | SA | X_aB | a • A → AA₁ | AS | SA | X_aB | a | b • A₁ → SA • X_a → a • B → b

Damit haben alle Produktionen die zulässige Form A → BC oder A → a, und die Grammatik befindet sich in Chomsky-Normalform.