Suche Home Einstellungen Anmelden Hilfe  

2.3.3 Chomsky-Normalform (CNF)

Beispiel: Umwandlung von Gkuchen
Gkuchen-CNF = (N',T,P',S)
Regeln P':
S -> Trocken Nass
-im CNF-Format, ohne Änd. zu P'
S -> Trocken S Nass
-nicht im CNF-Format, zu P':
S-> Trocken Sneu
Sneu->S Nass
Trocken -> MehlMehlZuckerZucker
-nicht im CNF-Format, zu P':
Trocken->Mehl Mehlneu
Mehlneu->Mehl Zuckerneu
Zuckerneu->Zucker Zucker
Nass ->EiÖl
-nicht im CNF-Format, zu P':
Nass->Ei Öl
weiterhin:
Mehl->Mehl
Zucker->Zucker
Ei->Ei
Öl->Öl

N' = N U {Sneu,Mehlneu,Zuckerneu,Mehl, Zucker,Ei,Öl}

Üben mit dem paté-Tool

Die Umwandlung einer kontextfreien Grammatik in die Chomsky-Normalform ist manchmal notwendig, damit bestimmte Parser, wie z.B. der Cocke-Younger-Kasami-Parser, kontextfreie Grammatiken verarbeiten können.

Eine kontextfreie Grammatik ist in CNF, wenn jede Regel in einer der folgenden Formen ist.

  1. A -> BC
  2. A -> a
  3. Wenn das leere Wort Teil der Sprache ist, dann gibt es eine Regel S -> e und S darf in keiner rechten Regelseite vorkommen.
Für jede kontextfreie Grammatik gibt es eine äquivalente Grammatik in CNF.

Vorgehen: Aus einer kfr. Grammatik G ohne Kettenregeln wird eine Grammatik G' in CNF konstruiert. Startsymbol und Terminalalphabet bleiben gleich.

Voraussetzung: G enthält keine Kettenregeln (Regeln der Form: A -> B) und G ist e-frei.

  • Regeln, die bereits dem CNF-Format genügen, werden zu P' hinzugefügt. Das sind Regeln der Form A -> a, A -> BC und S-> e. (A, B, C aus N, a aus T)
  • Für Regeln, bei denen die rechte Regelseite länger als 2 ist, werden modifizierte Regeln P' hinzugefügt:
    • Jedes Terminal a wird durch ein Nichtterminal a' ersetzt.
    • Die Regel wird durch eine Folge von Regeln mit einer Länge der rechten Seite von 2 ersetzt: für Ls -> A B C D ... Z in P wird zu P' hinzufgefügt:
      Ls -> A Bneu
      Bneu -> B Cneu
      Cneu -> C Dneu
      ...
      Yneu -> Y Z
    • Die mit neu gekennzeichneten Nichtterminale sind neue noch nicht in der Grammatik vorhandene Nichtterminale.
  • Für Regeln, bei denen die rechte Regelseite aus 2 Symbolen besteht, wovon mindestens eins ein Terminal ist, werden zu P' Regeln hinzugefügt, in denen jedes Terminal a durch ein Nichtterminal a' ersetzt wurde.
  • Für jedes durch ein Nichtterminal a' ersetztes Terminal a wird zu P' eine Regel a' -> a hinzugefügt. Das neue Nichtterminalalphabet enthält alle alten und alle im Verlauf der Konstruktion entstandenen Nichtterminalsymbole.

1   2   3   4   5 Greibach Normalform

Benutzer: Gast • Besitzer: matthias • Zuletzt geändert am: