Bestimmung der CNF

Algorithmus zur Bestimmung der Chomsky-Normalform

Eine betrachtete Grammatik G kommt folgendermaßen af Chomsky-Normalform:

  • Man mache G l-frei, wobei l für das leere Wort stehe
  • Man eliminiere alle reinen Umbenennungen
  • Man forme die Produktionsregel so um, dass die rechte Seite jeder Produktion entweder aus einem Terminalsymbol oder beliebig vielen Nonterminalsymbolen bestehe
  • Schlußendlich muss man jede Produktionsregel deren rechte Seite aus mindestens drei Nonterminalsymbolen besteht ersetzen – damit am Ende nun noch Regeln der Form NxT oder NxNN bestehen, wobei N die Menge der Nonterminalsymbole und T die Menge der Terminalsymbole darstelle.