Lexikon der Mathematik: Chomsky-Normalform
Grammatik, deren Regeln starken Restriktionen unterliegen.
Zu jedem Grammatiktyp (Chomsky–Grammatik) gibt es eine Normalform. Im einzelnen erlauben die Normalformen der vier Grammatiktypen Regeln folgenden Aufbaus (A, B, C, D sind Nichtterminalzeichen, a ein Zeichen des Alphabets):
- Typ 0: (A, BC), (BC, A), (A, a) sowie max. eine Regel der Form (A, ϵ);
- Typ 1: (A, BC), (AB, AD), (AB, CB), (A, a);
- Typ 2: (A, BC), (A, a);
- Typ 3: (A, Ba), (A, a) bzw. (A, aB), (A, a).
Ab Typ 1 ist außerdem die ϵ-treue Verwendung einer Regel (A, ϵ) erlaubt.
Zu jeder Grammatik vom Typ i kann eine äquivalente (d. h. die gleiche Sprache erzeugende) Grammatik in Normalform des Typs i effektiv konstruiert werden.
Copyright Springer Verlag GmbH Deutschland 2017
Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.