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 | -> |
  |
| -nicht im CNF-Format, zu P': |
| Trocken | -> | Mehl Mehlneu |
| Mehlneu | -> | Mehl Zuckerneu |
| Zuckerneu | -> | Zucker Zucker |
| Nass | -> |   |
| -nicht im CNF-Format, zu P': |
| Nass | -> | Ei Öl |
| weiterhin: |
| Mehl | -> | |
| Zucker | -> | |
| Ei | -> | |
| Ö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.
- A -> BC
- A -> a
- 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.
|
Greibach Normalform