Chomsky-Normalform

Eine Chomsky-Grammatik G = (N, T, P, S) ist genau dann in Chomsky-Normalform (CNF), wenn sie ausschließlich Ersetzungsregeln der folgenden Form enthält:

1. A → B C, mit A, B, C ∈ N;

2. A → a, mit A ∈ N, a ∈ T;

3. S → e.

D. h.: Alle Regeln, die nichtterminale Symbole einführen, verzweigen binär; alle Regeln, die terminale Symbole einführen, verzweigen unär; die leere Kette (e) wird nur durch eine Regel eingeführt, die das Startsymbol expandiert.

Kommentare

Die CNF wird von einigen Parsingalgorithmen (Satzanalyse) sowie in bestimmten Beweisen aus der Theorie der formalen Sprachen vorausgesetzt; sie steht in Opposition zu kontextfreien Grammatiken in Greibach-Normalform (GNF) und zu formalen Grammatiken in Kuroda-Normalform (KNF), die kontext-sensitive Sprachen generieren.

Grammatiken in CNF sind schwach äquivalent zu Typ-2-Syntaxen, d. h. für eine beliebige Typ-2-Grammatik G1 kann eine Syntax G2 in CNF konstruiert werden, die dieselbe Sprache erzeugt.

Link

Chomsky-Normalform in Norbert Fries, Online Lexikon Linguistik