In der formellen Sprachtheorie, wie man sagt, ist eine Grammatik ohne Zusammenhänge in Chomsky normale Form, wenn alle seine Produktionsregeln von der Form sind:

: oder

: oder

:

wo, und Nichtendsymbole sind, ist α ein Endsymbol (ein Symbol, das einen unveränderlichen Wert vertritt), ist das Anfang-Symbol, und ε ist die leere Schnur. Außerdem weder noch kann das Anfang-Symbol sein.

Jede Grammatik in Chomsky normale Form, ist und umgekehrt, jede Grammatik ohne Zusammenhänge ohne Zusammenhänge, kann in einen gleichwertigen umgestaltet werden, der in Chomsky normale Form ist. Mehrere Algorithmen, um solch eine Transformation durchzuführen, sind bekannt. Transformationen werden in den meisten Lehrbüchern auf der Automaten-Theorie, wie Hopcroft und Ullman, 1979 beschrieben. Wie hingewiesen, durch Lange und Leiß besteht der Nachteil dieser Transformationen darin, dass sie zu einem unerwünschten bloat in der Grammatik-Größe führen können. Die Größe einer Grammatik ist die Summe der Größen seiner Produktionsregeln, wo die Größe einer Regel ein plus die Länge seiner Rechte ist. Mit, um die Größe der ursprünglichen Grammatik anzuzeigen, kann sich die Größe-Explosion im Grenzfall von dazu erstrecken, je nachdem der Transformationsalgorithmus verwendet hat.

Alternative Definition

Eine andere Weise, Chomsky normale Form (z.B, Hopcroft und Ullman 1979 und Hopcroft zu definieren u. a. 2006) ist:

Eine formelle Grammatik ist in Chomskys reduzierter Form, wenn alle seine Produktionsregeln von der Form sind:

: oder:

wo, und Nichtendsymbole sind, und α ein Endsymbol ist. Wenn das Verwenden dieser Definition, oder das Anfang-Symbol sein kann. Nur jene Grammatiken ohne Zusammenhänge, die die leere Schnur nicht erzeugen, können in Chomskys reduzierte Form umgestaltet werden.

Das Umwandeln einer Grammatik Chomsky Normale Form

1. Führen Sie </dt> ein
2. : Führen Sie eine neue Anfang-Variable und eine neue Regel ein, wo die vorherige Anfang-Variable ist. </dd>
3. Beseitigen Sie alle Regeln </dt>
4. : Regeln sind Regeln der Form, wo und wo das variable Alphabet des CFG ist.
5. : Entfernen Sie jede Regel mit auf seiner rechten Seite (RHS). Für jede Regel mit in seinem RHS, fügen Sie eine Reihe neuer Regeln hinzu, die aus den verschiedenen möglichen Kombinationen von ersetzten oder nicht ersetzt dadurch besteht. Wenn eine Regel als ein Singleton auf seinem RHS hat, fügen Sie eine neue Regel hinzu, wenn bereits durch diesen Prozess nicht entfernt worden ist. Untersuchen Sie zum Beispiel die folgende Grammatik:
6. ::

::::

1. : hat eine Regel. Wenn entfernt zu sein, wir den folgenden bekommen:

::::

1. :Notice, dass wir für alle Möglichkeiten und so wir wirklich verantwortlich sein müssen, enden damit, 3 Regeln hinzuzufügen.
2. Beseitigen Sie alle Einheitsregeln
3. :
4. :After alle Regeln sind entfernt worden, können Sie beginnen, Einheitsregeln oder Regeln zu entfernen, deren RHS eine Variable und keine Terminals enthält (der mit CNF inkonsequent ist).
5. :: Zu entfernen
6. :: fügen Sie Regel hinzu, wenn das keine Einheitsregel ist, die bereits entfernt worden ist. </dd>
7. Räumen Sie restliche Regeln auf, die nicht in Chomsky normale Form sind. </dt>
8. : Ersetzen Sie dadurch, wo neue Variablen sind.
9. : Wenn, in obengenannten Regeln durch eine neue Variable ersetzen Sie und Regel hinzufügen Sie.

Siehe auch

• CYK Algorithmus
• Backus-Naur bilden
• Greibach normale Form
• Kuroda normale Form

Kommentare

• John E. Hopcroft und Jeffrey D. Ullman, Einführung in Automaten-Theorie, Sprachen und Berechnung, Addison-Wesley Publishing, Massachusetts, 1979 Lesend. Internationale Standardbuchnummer 0 201 02988 X. (Sieh Kapitel 4.)

• (Seiten 98-101 des Abschnitts 2.1: Grammatiken ohne Zusammenhänge. Seite 156.)

• (Seiten 237-240 des Abschnitts 6.6: vereinfachte Formen und normale Formen.)

• (Seiten 103-106.)
• Kohl, Richard. CFGs zu CNF (Chomsky Normale Form) am 17. Oktober 2007 umwandelnd. (pdf)
• Sipser, Michael. Einführung in die Theorie der Berechnung, 2. Ausgabe.