„Chomsky-Normalform“ – Versionsunterschied
| [gesichtete Version] | [gesichtete Version] |
K Bot: Ergänze: cs:Chomského normální forma | erster satz an den anfang ;) | ||
| Zeile 1: | Zeile 1: | ||
Die '''Chomsky-Normalform''' (Abk.: '''CNF''') ist ein Begriff aus der [[Formale Sprache|Theorie der formalen Sprachen]], einem Teilbereich der [[Theoretische Informatik|Theoretischen Informatik | Die '''Chomsky-Normalform''' (Abk.: '''CNF''') ist eine [[kontextfreie Grammatik]] mit einer besonders einfachen Struktur der [[Produktionsregel|Produktionen]]. Sie ist ein Begriff aus der [[Formale Sprache|Theorie der formalen Sprachen]], einem Teilbereich der [[Theoretische Informatik|Theoretischen Informatik]]. Sie ist nach dem [[Vereinigte Staaten|US]]-[[Linguist]]en [[Noam Chomsky]] benannt und kommt beim [[Cocke-Younger-Kasami-Algorithmus|CYK-Algorithmus]] zum Einsatz. | ||
Zu jeder kontextfreien Sprache gibt es eine Chomsky-Normalform. Deshalb kann aus jeder kontextfreien Grammatik <math>G</math> eine Chomsky-Normalform <math>G_{CNF}</math> konstruiert werden, die dieselbe Sprache erzeugt. Die Grammatik <math>G_{CNF}</math> wird dann auch eine Chomsky-Normalform der kontextfreien Grammatik <math>G</math> genannt. | Zu jeder kontextfreien Sprache gibt es eine Chomsky-Normalform. Deshalb kann aus jeder kontextfreien Grammatik <math>G</math> eine Chomsky-Normalform <math>G_{CNF}</math> konstruiert werden, die dieselbe Sprache erzeugt. Die Grammatik <math>G_{CNF}</math> wird dann auch eine Chomsky-Normalform der kontextfreien Grammatik <math>G</math> genannt. | ||
Version vom 30. Juni 2008, 04:53 Uhr
Die Chomsky-Normalform (Abk.: CNF) ist eine kontextfreie Grammatik mit einer besonders einfachen Struktur der Produktionen. Sie ist ein Begriff aus der Theorie der formalen Sprachen, einem Teilbereich der Theoretischen Informatik. Sie ist nach dem US-Linguisten Noam Chomsky benannt und kommt beim CYK-Algorithmus zum Einsatz.
Zu jeder kontextfreien Sprache gibt es eine Chomsky-Normalform. Deshalb kann aus jeder kontextfreien Grammatik eine Chomsky-Normalform konstruiert werden, die dieselbe Sprache erzeugt. Die Grammatik wird dann auch eine Chomsky-Normalform der kontextfreien Grammatik genannt.
Eine Erweiterung der Chomsky-Normalform auf kontextsensitive Grammatiken stellt die Kuroda-Normalform dar.
Definition
Eine formale Grammatik ist in Chomsky-Normalform, wenn jede Produktion eine der folgenden Formen hat:
wobei , und Nichtterminalsymbole sind und ein Terminalsymbol ist. ist das Startsymbol und das leere Wort. Wenn die Produktion zur Grammatik gehört, dann darf nicht auf der rechten Seite einer Produktion stehen.
Lässt man bei der ersten Produktion auf der rechten Seite beliebig viele anstatt zwei Nichtterminalsymbole zu, so spricht man von einer schwachen Chomsky-Normalform.
Konstruktion einer Chomsky-Normalform
Liegt eine kontextfreie Grammatik vor, so lässt sich daraus schrittweise eine Chomsky-Normalform generieren, die dieselbe Sprache erzeugt:
- Eine schwache Chomsky-Normalform erzeugen
- Jedem Terminalsymbol wird ein Nichtterminalsymbol zugeordnet. Auf der rechten Seite jeder Produktion werden sämtliche Terminalsymbole durch das entsprechende Nichtterminalsymbol ersetzt. Abschließend werden alle Produktionen der Grammatik hinzugefügt.
- Rechte Seiten mit mehr als zwei Nichtterminalen ersetzen
- Sind auf der rechten Seite einer Produktion mehr als zwei Nichtterminale, so werden zwei benachbarte Nichtterminale durch ein neues Nichtterminal ersetzt. Die Produktion wird zur Grammatik hinzugefügt. Dies wiederholt man solange, bis keine Produktion mit mehr als zwei Nichtterminalen mehr vorkommt.
- -Produktionen entfernen
- Streiche die Regeln .
- Falls Regeln der Art mit existieren, ersetze sie durch .
- Hierbei muss man aufpassen, dass man das Resultat der Abbildungen nicht inhaltlich verändert. Beispiel: eine Abbildung der Startvariable auf eine oder mehrere Variablen die wiederum auf abgebildet werden, sprich die Erzeugung des leeren Wortes, muss auch bei der Grammatik in Chomsky-Normalform möglich sein. bildet sozusagen eine Ausnahme der obigen Definition, da es die Abbildung geben darf.
- Kettenregeln (Produktionen der Form A→B) entfernen
- Wenn man eine Kettenregel, d. h. eine Produktion der Form , entfernt, fügt man für jede vorhandene Produktion der Form eine neue Produktion hinzu, falls diese keine bereits entfernte Kettenregel ergibt. ist hierbei ein beliebiges Wort aus Nichtterminalen.
Quellen
- Grzegorz Rozenberg, Arto Salomaa: Handbook of Formal Languages. Volume 1. Word, Language, Grammar. Springer-Verlag, 1997, ISBN 3-540-60420-0, S. 124–125
Weblinks
- Programm zur Berechnung von Chomsky-Normalformen (Java-Applet)
