Kuroda-Normalform

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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.

Definition[Bearbeiten]

Eine formale Grammatik ist in Kuroda-Normalform (kurz KNF), wenn alle Produktionen die folgende Form haben:

  • A \rightarrow a
  • A \rightarrow B
  • A \rightarrow BC
  • AB \rightarrow CD

wobei A, B, C und D Variablen sind und a ein Terminalsymbol ist.

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

Eigenschaften[Bearbeiten]

  • Jede Grammatik in Kuroda-Normalform ist eine monotone Grammatik.
  • Zu jeder monotonen Grammatik G_1 mit \varepsilon\notin L(G_1) existiert eine monotone Grammatik G_2 in Kuroda-Normalform, die die gleiche Sprache erzeugt, das heißt, L(G_1)=L(G_2). G_2 wird dann auch eine Kuroda-Normalform der monotonen Grammatik G_1 genannt.

Umwandlung einer Grammatik in Kuroda-Normalform[Bearbeiten]

Sei G_1=(V_1,\Sigma,P_1,S) eine monotone Grammatik mit \epsilon\notin L(G_1). Eine Kuroda-Normalform G_2=(V_2,\Sigma,P_2,S) von G_1 kann so konstruiert werden:

  • Alle in P_1 auftretenden Terminalsymbole a werden jeweils durch eine neue Variable A_a ersetzt, und für jedes Terminalsymbol a wird die neue Produktionen A_a\rightarrow a eingeführt.
  • Jede Produktion der Form A\rightarrow A_1A_2\dotso A_k ersetzt man durch folgende neuen Produktionen: A\rightarrow A_1B_1, B_i\rightarrow A_{i+1}B_{i+1} für alle i\in\{1,\dotsc,k-3\} und B_{k-2}\rightarrow A_{k-1}A_k. Dabei seien B_1,\dotsc,B_{k-2} neue Variablen.
  • Jede Produktion der Form A_1A_2\dotso A_l\rightarrow B_1B_2\dotso B_k, 2\leq l\leq k mit 3\leq k ersetzt man durch folgende neuen Produktionen: A_1A_2\rightarrow B_1C_1, für alle i\in\{1,\dotsc,l-2\}: C_i A_{i+2}\rightarrow B_{i+1}C_{i+1}, für alle i\in\{l-1,\dotsc,k-3\}: C_i\rightarrow B_{i+1}C_{i+1} und C_{k-2}\rightarrow B_{k-1}B_k. Dabei seien C_1,\dotsc,C_{k-2} neue Variablen.

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

Révész-Normalform[Bearbeiten]

Jede monotone Grammatik G_1=(V_1,\Sigma,P_1,S) in Kuroda-Normalform kann in eine kontextsensitive Grammatik G_2=(V_2,\Sigma,P_2,S) in Révész-Normalform überführt werden. Dazu werden für jede Produktionsregel der Form AB \rightarrow CD \in P_1 zwei neue Nichtterminale W,Z\in V_2 eingeführt und die Regel durch vier Regeln ersetzt:

  • AB \rightarrow AZ
  • AZ \rightarrow WZ
  • WZ \rightarrow WD
  • WD \rightarrow CD

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

  • AB \rightarrow AC
  • AB \rightarrow CB
  • A \rightarrow BC
  • A \rightarrow B
  • A \rightarrow a

Dabei sind A, B und C Variablen und a ist ein Terminalsymbol.

Zu jeder kontextsensitiven Grammatik G_1 mit \varepsilon\notin L(G_1) existiert eine kontextsensitive Grammatik G_2 in Kuroda-Normalform, die die gleiche Sprache erzeugt, das heißt, L(G_1)=L(G_2).

Literatur[Bearbeiten]

  •  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).