WikiDer > Chomsky-Normalform
Chomsky-Normalform ist ein Konzept aus dem Theoretische Informatik, insbesondere der Bereich von formale Sprachen. Die Chomsky-Normalform ist ein Merkmal, das a formale Grammatik besitzen kann oder nicht.
Die Chomsky-Normalform ist aus der Sicht interessant Berechenbarkeit; viele Beweise machen davon Gebrauch. Außerdem führen Grammatiken in der Chomsky-Normalform zu effizienten Algorithmen; es ist ein beispiel CYK-Algorithmus, die entscheidet, ob eine gegebene Zeichenfolge von einer gegebenen Grammatik erzeugt werden kann.
Die Chomsky-Normalform ist benannt nach Noam Chomsky, das amerikanischLinguist dass die Chomsky-Hierarchie erfunden.
Definition
Eine formale Grammatik ist in Chomsky-Normalformdann und nur dann, wenn alle Produktionsregeln , dass Grammatik eine der folgenden Formen aufweist:
- ein → BC
- ein →
- so →
wahr ein, B und C Nichtterminale Symbole sind, α a Klemmensymbol (ein Symbol mit einem konstanten Wert), so ist das Startsymbol und ε ist die leere Zeichenfolge. Außerdem darf das Startsymbol nicht B oder C sein.
Jede Grammatik in Chomsky-Normalform ist kontextfrei, und jede kontextfreie Grammatik kann effizient in eine äquivalente Grammatik in Chomsky-Normalform umgewandelt werden.
Außer der Produktionsregel so → ε (wird nur verwendet, wenn die Grammatik den leeren String erzeugen kann), alle Produktionsregeln einer Grammatik in Chomsky-Normalform werden erweitert; Bei der Ableitung eines Strings hat also jeder String aus Terminalsymbolen und Nichtterminalsymbolen die gleiche Länge oder nur 1 Element mehr als der vorherige String. Die Ableitung einer Zeichenkette der Länge nein ist immer präzise 2n - 1 Schritte lang. Und da alle Produktionsregeln, die nicht-terminale Symbole ableiten, ein nicht-terminales Symbol in genau 2 nicht-terminale Symbole umwandeln, ist die Syntaxbaum basierend auf einer Grammatik in Chomsky-Normalform immer a Binärbaum. Die Höhe dieses Baumes hat als maximale Höhe die Länge der Schnur.
Alternative Definition
Eine Reihe von Quellen definiert die Chomsky-Normalform wie folgt, die etwas anders ist:
EIN formale Grammatik ist in Chomsky-Normalformdann und nur dann, wenn alle Produktionsregeln in dieser Grammatik haben eine der folgenden Formen:
- ein → BC
- ein →
wahr ein, B und Cnicht-terminale Symbole be, und α a Klemmensymbol ist. Per Definition ist das Startsymbol erlaubt B oder C sein.
Der Unterschied zwischen dieser Definition und der vorherigen besteht darin, dass eine Grammatik, die diese Definition erfüllt, keine leere Zeichenfolge erzeugen kann. Dies tut jedoch keinen Abbruch der Tatsache, dass jede kontextfreie Grammatik dieser Sprache l akzeptiert, kann effizient in eine Grammatik in Chomsky-Normalform umgewandelt werden, die diese Sprache L - {ε} akzeptiert. Der Hauptvorteil dieser Definition besteht darin, dass Beweise etwas einfacher werden, da kein Schritt in einer Ableitung die Länge des resultierenden Strings reduzieren kann. Der Nachteil ist, dass Maßnahmen ergriffen werden müssen, wenn die Originalgrammatik ε erzeugt.
Siehe auch
Verweise
- Michael Sipser, Einführung in die Rechentheorie, PWS Publishing. ISBN 0-534-94728-X, 1997.
- Johannes Martin, Einführung in die Sprachen und die Rechentheorie, McGraw Hill, 2003. ISBN 0-07-232200-4 .