Kuroda-Normalform

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

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

• $A\to a$
• $A\to B$
• $A\to BC$
• $AB\to 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

• Jede Grammatik in Kuroda-Normalform ist eine monotone Grammatik.
• Zu jeder monotonen Grammatik $G_1$ mit $\epsilon \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

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

• Alle in $P_1$ auftretenden Terminalsymbole $a$, welche nicht alleine auftreten, werden jeweils durch eine neue Variable $A_a$ ersetzt, und für jedes Terminalsymbol $a$ wird die neue Produktionen $A_a\to a$ eingeführt.
• Jede Produktion der Form $A\to A_1{A}_2\dots A_k$ ersetzt man durch folgende neuen Produktionen: $A\to A_1{B}_1$, $B_i\to A_{i+1}{B}_{i+1}$ für alle $i\in \{1,\dots ,k-3\}$ und $B_{k-2}\to A_{k-1}{A}_k$. Dabei seien $B_1,\dots ,B_{k-2}$ neue Variablen.
• Jede Produktion der Form $A_1{A}_2\dots A_l\to B_1{B}_2\dots B_k$, $2\le l\le k$ mit $3\le k$ ersetzt man durch folgende neuen Produktionen: $A_1{A}_2\to B_1{C}_1$, für alle $i\in \{1,\dots ,l-2\}$: $C_i{A}_{i+2}\to B_{i+1}{C}_{i+1}$, für alle $i\in \{l-1,\dots ,k-3\}$: $C_i\to B_{i+1}{C}_{i+1}$ und $C_{k-2}\to B_{k-1}{B}_k$. Dabei seien $C_1,\dots ,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

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

• $AB\to AZ$
• $AZ\to WZ$
• $WZ\to WD$
• $WD\to CD$

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

• $AB\to AC$
• $AB\to CB$
• $A\to BC$
• $A\to B$
• $A\to a$

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

Zu jeder kontextsensitiven Grammatik $G_1$ mit $\epsilon \notin L(G_1)$ existiert eine kontextsensitive Grammatik $G_2$ in Révész-Normalform, die die gleiche Sprache erzeugt, das heißt, $L(G_1)=L(G_2)$.

Literatur

• Vorlage:Literatur