Kuroda-Normalform

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Die Kuroda-Normalform ist ein Begriff der Theoretischen Informatik, der im Zusammenhang mit kontextsensitiven Sprachen von Interesse ist. Sie ist nach dem Linguisten Sige-Yuki Kuroda benannt und beschreibt eine Normalform der monotonen Grammatiken, also eine Teilmenge der monotonen Grammatiken, die gegenüber der Menge aller monotonen Grammatiken nichts an Ausdrucksstärke einbüßt. Die Bedeutung der Kuroda-Normalform liegt in der sehr einfachen Struktur der Produktionen. Weil monotone Grammatiken und kontextsensitive Grammatiken gelegentlich nicht unterschieden werden, wird die Kuroda-Normalform auch als Normalform der kontextsensitiven Grammatiken bezeichnet.

Die Kuroda-Normalform ist eine Verallgemeinerung der Chomsky-Normalform, die eine Normalform für kontextfreie Grammatiken ist.

Eine formale Grammatik ist in Kuroda-Normalform (kurz KNF, nicht zu verwechseln mit „KNF“ – Konjunktive Normalform), wenn alle Produktionen die folgende Form haben:

wobei , , und Variablen sind und ein Terminalsymbol ist.

Falls die zweite und die vierte Regelform nicht vorkommen, liegt die Grammatik in der Chomsky-Normalform vor.

  • Jede Grammatik in Kuroda-Normalform ist eine monotone Grammatik.
  • Zu jeder monotonen Grammatik mit existiert eine monotone Grammatik in Kuroda-Normalform, die die gleiche Sprache erzeugt, das heißt, . wird dann auch eine Kuroda-Normalform der monotonen Grammatik genannt.

Umwandlung einer Grammatik in Kuroda-Normalform

[Bearbeiten | Quelltext bearbeiten]

Sei eine monotone Grammatik mit . Eine Kuroda-Normalform von kann so konstruiert werden:

  • Alle in auftretenden Terminalsymbole , welche nicht alleine auftreten, werden jeweils durch eine neue Variable ersetzt, und für jedes Terminalsymbol wird die neue Produktionen eingeführt.
  • Jede Produktion der Form ersetzt man durch folgende neuen Produktionen: , für alle und . Dabei seien neue Variablen.
  • Jede Produktion der Form , mit ersetzt man durch folgende neuen Produktionen: , für alle : , für alle : und . Dabei seien neue Variablen.

Die so erzeugte Grammatik ist in Kuroda-Normalform und produziert dieselbe Sprache wie die Grammatik zuvor.

Révész-Normalform

[Bearbeiten | Quelltext bearbeiten]

Jede monotone Grammatik in Kuroda-Normalform kann in eine kontextsensitive Grammatik in Révész-Normalform überführt werden. Dazu werden für jede Produktionsregel der Form zwei neue Nichtterminale eingeführt und die Regel durch vier Regeln ersetzt:

Eine kontextsensitive Grammatik ist in Révész-Normalform, wenn alle Produktionen die folgende Form haben:

Dabei sind , und Variablen und ist ein Terminalsymbol.

Zu jeder kontextsensitiven Grammatik mit existiert eine kontextsensitive Grammatik in Révész-Normalform, die die gleiche Sprache erzeugt, das heißt, .

  • Benedek Nagy: Derivation Trees for Context-Sensitive Grammars. In: Automata, Formal Languages and Algebraic Systems: Proceedings of AFLAS 2008. World Scientific Pub Co, 2008, ISBN 981-4317-60-8, S. 182 (eingeschränkte Vorschau in der Google-Buchsuche).