Linguipedia: New page: 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...

2007-07-02T13:59:52Z

New page: 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...

New page

Eine [[Chomsky-Grammatik]] G = (N, T, P, S) ist genau dann in '''Chomsky-Normalform''' (CNF), wenn sie ausschließlich [[Ersetzungsregel]]n 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 [[Regel]]n, 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===
[http://www2.rz.hu-berlin.de/linguistik/institut/syntax/onlinelexikon/C/chomsky_normalform.htm Chomsky-Normalform] in Norbert Fries, Online Lexikon Linguistik

{{wb}}
[[Category: General]]

Chomsky-Normalform - Revision history

Linguipedia: New page: 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...