Direkt zum Inhalt

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.

Lesermeinung

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.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos